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.