I did one little breadboard project with a 3.3V GPS device, the only 3.3V device I have interfaced so far. I did it with an ATMega328P so I didn't have 3.3V from an Arduino.
As for power, I used this regulator which seems to have a good reputation, works fine, multimeter says it is spot on:http://www.jameco.com/webapp/wcs/stores/servlet/Product_10001_10001_897188_-1
Now the nice thing is that the GPS could be interfaced to the INPUTs of the ATMega328P fine - 3.3V drives the inputs without any trouble, and the GPS itself needs no input, it starts sending data once it has it. So I was set there.
If you need to send output to a 3.3V device you need to use a level converter like the one mentioned above which seems to be bidirectional and intelligent and out of stock. As an alternate, there is this not quite as elegant solution:https://www.sparkfun.com/products/8745
But it is now out of stock too. What gives with all these level converters out of stock?