I'm a fan of the xx1117's as 3.3v regulators (xx is some set of letters like LM or what not). They are a good choice for taking 5v down to 3.3v in my mind.
As for the 5v regulator, 7805's are always the ones I jump to. Widely available, fairly cheap.
In terms of efficiency, its never really something I have needed to worry about in my projects so can't be much help there.
ElCaron:
Arduino goes [Input]->5V->3.3V, as far as I understand. Would I want to use the same components? Checking Ebay, they don't seem to be common.
The ones Arduino use seem a little weird and uncommon as they are surface mount components, and really in part I imagine they are chosen for reliability, size, and more importantly cost.
I see no reason why you should hunt around for them when you can get others that do the same job.
ElCaron:
What would I use if I only wanted 3.3V? What would be the best choice for battery power (5V or 3.3V)?
If you only want 3.3v, you can use the 3.3v version of the xx1117. It has a fairly wide range (I think 15v is the max input voltage).
If you are looking at battery powered, it really depends on the battery. If you have a 9v battery, then go with 5v, as there is less wasted in the regultation. Alternatively you could look at switching regulators which are much more efficient as they convert current to voltage (or vice versa) which means you are not dissipating the excess voltage as heat. If you look around, there are a number of breakout boards for step-up/step-down.