Lithium batteries are restricted. Other types aren't (but sometimes the post office employees are too lazy or don't care about the rules and prefer to simply mass-refuse any kind of battery)
Power supplies don't have supercapacitors (well, most regular ones).
Supercapacitors are regularly used in products (Xbox 360 for example) but mostly for battery backup replacement... hold important settings, store time etc... so very low current devices.
How much your product will last on supercapacitors will depend on its current consumption and the voltage you want and how you use the energy stored in the supercap.
If you just connect the supercapacitor to your product, it's not going to last long, because as soon as the supercapacitor discharges down to 1.8v (the lowest voltage your product runs at), your product will die. From 0v to 1.8v there's still more than 50% of the energy stored in the supercap.
You would have to reduce the current consumption of your product, and you'll have to run it at lowest voltage possible and the you would normally use a boost regulator to convert a wide range of input voltage to the voltage your product needs.
The boost regulator will make a lot of difference, there are boost regulators that boost voltages as low as 0.6v to higher voltages (like
isl9111 for example), other regulators need at least 1.2-2v to work.
I've personally used a 25F 2.7v supercapacitor along with LT1308 to boost 1v-2.7v to 6v (because while the meter works with as low as 3v, it shows low battery at around 5.7v) to run a Uni-T UT61E for a bit over an hour... I've made a series of videos about it
here. LT1308 (see its page
here) works with 1v or more and is more efficient when the input-output difference is smaller.. were it to boost to 2.5v it would have been a different story. At 6v out, it's only about 70-75% efficient.
There's also SEPIC regulators, which can take something like 2.7v and convert down to 1.8v or whatever your product uses, and when the supercapacitor voltage goes down below 1.8v, they can switch to a boost mode, raising the voltage to 1.8v.. for example
LT1613 is one of those.