It also depends on how you'll use it. Personally I anticipated a lot of tinkering and didn't want to do a lot of soldering so I opted for a USB Duemanov-whatever; I bought one from China on eBay for about 20 USD and another from SoarkFun for about 30 USD (the build quality of the Chinese one from eBay was better!)
But if you know exactly what you're going to do then you can get a SUPER cheap model like the Really Barebones Arduino from Modern Devices.
But here's the trick: if you don't have an FTDI cable then the cost of a small Arduino like the barebones arduino + FTDI cable comes out to be about the same as just buying a USB Duemenova!
So I recommend buying an Arduino off eBay, especially from a Chinese dealer; they usually have free shipping and cheaper prices than stores 