If I can only power the chip with 5v, how on earth could I use it to control 12v LEDs? Is there a way I can hook those little guys up to a different power source? IE 5v Red wire to power atmega and other bits, then yellow 12v to power the LEDs?
You can use relays or transistors. For my project with 12v lighting, I used transistors so that I could dim the lights if I wanted (PWM), plus I didn't want relay contact noise.
Here is a pic of a small "module" that I made with inputs from the arduino and then outputs for the lights. The LEDs on the board were used for troubleshooting, the LED lights when the input from the Arduino has power. It also let me code on the bench without having the lights connected, yet I could see what was going on.
If I remember correctly (how fast it fades), I ran the 12v + straight to the lights, and was switching ground with a TIP-120 transistor. The TIP-120s are overkill for what I needed (they support much more power) but I had them handy and don't need to worry about overheating them!
This method requires one Arduino pin, one transistor and one resistor for each 12v device switched. (The module above supports switching 5 devices) You would need to pick the right transistor based on the power of the 12v device you are switching. I also added the one red LED per output, but you likely wouldn't want the extra light in your project. I chose to do this on a separate board from the rest of my project just to keep things modular, that was my choice given the number of connections in my project and the desire to change it frequently, there is no special need to isolate these devices from the rest of your project.