If you already have the Arduino board and components you can check out Jeremy Blum's tutorials on his website here. If you do not have the required materials you can search around the internet for a beginner kit, I have heard Adafruit and Sparkfun are good places to look. Hope this helped and best of luck on your endeavors.
In case the hyperlink doesn't work just copy and paste this:
Actually, I believe with all my heart, the best place to start is Youtube.com via a search for "Arduino" + your_native_language. Then move on to Youtube.com videos in any other language the new 'Duino user can understand.
My take on this (it's how i'm tying myself) is to get a kit (as Orion suggested) and follow the guides that are normally provided with that (Oomlout do a good one if you are in the UK, as do Earthshine electronics).
I'd also get a couple of good books that you can learn from and will also allow you to pick up ideas and whatnot when you are not in front of a computer (I commute 1:20 each way a day, so I have a lot of downtime).
I'd recommend 'Getting Started with Arduino' by Massimo Banzi (Who came up with the idea of Ardunio originally) and also 'The Arduino Cookbook' by Michael Margolis. Dr Simon Monk who frequents these forums has also written quite a few books, i've got 'Programming Arduino - Getting started with sketches' which is also worth a read.
