I know Photoshop, but have never used Premiere. I installed CS4 and wanna learn the basics, i.e. how to cut footage together. What's the best place with newbie tutorials / articles to learn this stuff? Video tutorials would be great. Thanks.

Start here: http://tv.adobe.com/#pd+Premiere%20Pro

Similar as above:
http://tv.adobe.com/#ch+How To
Adobe Premiere Pro CS4 * Using Adobe*Premiere*Pro CS4 (http://help.adobe.com/en_US/PremierePro/4.0/index.html)
http://www.adobe.com/designcenter/video_workshop/?id=vid0090
http://tv.adobe.com/?trackingid=EKAKT#
http://tv.adobe.com/#vi+f1510v1005
https://www.adobe.com/cfusion/event/index.cfm?id=1437291&event=set%5Fregistered&loc=en%5Fus
Adobe - Online events : eSeminars (http://www.adobe.com/cfusion/event/index.cfm?event=list&loc=en_us&type=eseminar&product=Creative+Suite&interest=&audience=&monthyear=&sdid=DNSCI)

I really like lynda.com. It's set up to take you from start to finish and has a great selection of courses. You can try out the first lessons for free and covers almost anything you would need.