You need four pieces of information
1) How much current do you need (in amps)?
2) How long do you want to run your circuit from the cap (in seconds)?
3) What it the largest voltage (normally the regular operating voltage) which will be applied? and
4) What is the lowest voltage out of the capacitor which will still allow the circuit to function?
Let's call 1) i, let's call 2) $\delta$t, 3) is Vmax, and 3) minus 4) is $\delta$V.
The relationship between time, voltage and current in a capacitor with a value of C in Farads is $${\frac{i}{C} = \frac{dV}{dt}}$$
For a constant i, which is a reasonable first approximation in this case, this becomes $${\frac{i}{C} = \frac{{\Delta}V}{{\Delta}t}}$$, or$${C = \frac{i{\Delta}t}{{\Delta}V}}$$ and the capacitor must have a voltage rating of Vmax.
To walk you through this, lets say you need .25 amps for 5 minutes (600 seconds). Let's say your battery puts out 3.7 volts when fresh, and your circuit will work down to a battery voltage of 3.0 volts. Then $$C = {\frac{(.25)(600)}{(3.7 - 3.0)}}$$ $$C = {\frac{150}{0.7}}$$
and you need a 214 Farad supercap with a voltage rating of 3.7 volts minimum.
EDIT - As Brian Drummond has pointed out, supercaps often have a high internal resistance. If you want to take this into consideration (and you had better do so), you need to quantify the resistance R of the cap at the current level which you are using. Then the capacity calculation remains the same, but if the capacitor voltage rating is Vcap, instead of being Vmax, $$Vcap = Vmax + (iR)$$ In the above example, if the ESR of the supercap is 20 ohms, $$Vcap = 3.7 + (.25)(20)$$ and $$Vcap = 8.7$$ In this case you would definitely need to find a different supercap.
The problem with capacitors is not quick discharge capability, it is energy density, and particularly the energy density of types of capacitor that can discharge very quickly.
There are apparently some batteries on the market that use graphene in their design. However, the use of graphene is a research area that some are claiming has great potential, not something that has a huge proven potential.
I believe that there are superconductor-based inductive energy storage systems that have been installed, proven and currently offered for sale. However they are of the scale that would be transported on a large truck or rail car, not something that has potential for anything near hand-held.
It is very doubtful that a useful hand-held rail-gun is any closer to reality than a nuclear fusion powered automobile.
Added information about inductive energy storage
The difficulty with small scale superconductor-based inductive energy storage systems is that there is a substantial balance of system (BOS). The BOS is all of the required components and equipment in addition to the basic energy storage component. Refrigeration equipment and insulation is required to get the superconductive material cold and keep it cold. There are also charging and discharging or energy transfer systems.
Best Answer
It's possible that there may be niche applications where that is true (although none come to mind with a quick musing) but for even 'ordinary everyday' batteries they have a way to go yet as regards either mass or energy densities.
BUT, as can be seen below, they have some utterly fantabulous specs that batteries cannot hope to match. eg 1,000,000 cycle life, 1000A+ max discharge current, 100A test current, ... !
Modern high end NimH batteries have energy densities about the same as typical LiIon cells. I'll use a typical NimH AA cell for comparison, but results would be similar for Lion or LiPo. LiFePO4 has perhaps half the energy density of LiIon but even LiFePO4 is far more energy dense that good supercaps.
An eg AA (14500) NimH cell weighs about 33g and provides about say 2500 mAh at 1.1V mean. That's conservative. Energy = 2.5 Ah x 3600 s/hr x 1.1V = 9900 Joule.
Say 10,000 Joule.
A capacitor discharged from Vmax to Vmax/4 delivers 15/16 of it's energy (as E= 0.5 x C x V^2).
So discharging a say 2.7V capacitor to about 0.675V uses most of the stored energy and is still a high enough voltage for operating a boost converter. A boost converter at around 0.6V has lower efficiency than at say >= 1 V but efficiency is liable to be acceptable if accessing stored Joules is more important than maximising efficiency.
E = 0.5 x C x V^2 x 15/16 = 9900 so
C = E x 2 x 16/15 /V^2 = 2897 F
Say ~= 2500 to 3000 F at 2.7V.
Digikey cheapest in that range are Maxell K2 series
Cycle life
Short circuit current - Amp (also abs max for caps)
Toperate C max/min
Lifetimes:
A 1,000,000 cycle life is quoted but temperature modified calendar life is liable top be the limiting factor. Data sheets for several brands claim 10 year lifetimes at 25 C with the usual Arrhenius equation effect of halving lifetime for each 10 degree C rise in operating temperature. If due care was not taken there are many locations where a 35c operating temperature could occur very easily, with a consequent 5 year typical lifetime. There will be applications where forced air cooling and even heatsinking may be useful.
Here's a teardown of a satellite interfaced fishing buoy - Mikes electric stuff August 2014.
At this point: https://youtu.be/mY2X-ZQpnvY?t=475
You see this. Obviously the cost is irrelevant in the circumstances and the advantages outweigh the fact that this has about the same storage capacity as a good AA Nimh cell. There is space for a second one, but only one is fitted.