Instead of using a linear regulator, I would recommend using a buck/boost regulator. These switching regulators can achieve efficiencies of up to 96% (and theoretically they could be perfect if all the parasitic impedances vanished). What is even cooler is that it allows the super-cap to operate across a range of voltages that can be LOWER than your desired output voltage.
Basically, this would take energy from the super-cap and push it into a normal capacitor. The regulating chip would monitor the secondary cap's voltage and squirt just enough current to it through an inductor to keep it at the correct voltage. The inductor smooths things out so that even though you are giving it pulses of current, the voltage is relatively smooth.
I didn't get into enough detail to really understand the circuit, so take a look at the following link if you are interested.
http://en.wikipedia.org/wiki/Buck-boost_converter
For construction, picking a part really depends on your input voltage, output voltage, and current. TI, Linear and National all make really nice buck/boost regulators. Personally, my favorite is the TPS63000.
Also, if you _know_ that your supercap will always have more voltage than you need, use a buck regulator. If you know it will always have less voltage, use a boost regulator.