is there a separate Arduino for each of these controllers or can I just swap a 168 into the Uno and build the project?
Adding to retrolefty's comments: the 2560 would have to have its own board, because it's physically very different from the 168 and 328.
There are some folks who have ported subsets
of the Arduino libraries to some
of the ATTiny series, but not to all of them. For now, you should stick to the ATMegas: they're well-supported, and the cost is only slightly higher. As you learn more, you may decide to use the ATTiny chips for some projects, and you can figure out how you want to do that (with/without the "Arduino Lite" software) then.
Will I also need to buy a programmer like STK500 to get started?
Not to get started, if you stick with the ATMega series: you can buy them with the bootloader already burned in for only a dollar or so more than the "raw" chip cost. When I checked last year, Modern Devices
had the best deals on "Arduino-ized" chips, but NKC
was also reasonable. I really like Modern's RBBB for building Arduinos into projects: they're cheap, compact, and easy to mount on an IC-pattered perfboard or a stripboard.