First, if you've gone through the adrenaline rush and panic of having JUST deleted for formatted your SD card or flash, calm for a bit and know there is hope.
The FIRST thing you should do, after the format or erasure, is remove the card from the device and slide the write protect switch to protect any further data from accidentally being written to it, making it read only. Some flash/memory sticks also have this feature, but not many.
If the card is in the process of formatting, and you realize it, don't yank the card out as this may cause total data corruption on the card and make recovery less likely. Let it actually finish the format finish as once it's begun, it usually only tells the card's file system that space occupied by the previous data is now free to be overwritten, rather than actually erasing the files.
By NO MEANS should you attempt to put any other data on the card. No more video, photos, files, - NOTHING! Doing so may overwrite the erased data and make it completely unrecoverable.
Second, Now that you have your SD card write protected, you'll need an SD card reader. This can be the camera itself connected to the computer via a USB cable, an external USB media card reader, or one integrated into your computer. Usually flash cards are formatted with the FAT or FAT32 file system so they should be readable by most operating systems, and mounted automatically as a drive letter, as in the case of most any version of Windows.
From here you should be able to use a file-manager, such as Windows Explorer in the case of Windows, to access the drive that has appeared on your computer. It will most likely appear totally empty as it has just been formatted, or in the case of an accidental erasure, you may see file folders/directories on the card that contain additional data.
You will also need enough free disk space on another drive, most likely your computer's hard drive, to store data you may recover from the card. I would recommend that you have at least enough free space to accommodate the size of the card. If you have a 4 gigabyte flash card, you should have at least that much free space located on the drive you intend to recover the data. You also may want to create a file folder/directory specifically for the recovered data. Name it "Card Recovery" or whatever you wish, just so you know where your data is going.
Once you have verified that you can mount your SD card or memory stick as a drive on your system, there are several "undeleted/unformat/data recovery" programs available for free.
One exceptional program that is totally free is called Recuva.
You can download it here: http://www.piriform.com/recuva
It does an excellent job at recovering data from formats, or deletions, for data of many other types. As with any software, read the documentation so you know how to use it before-hand, and avoid the temptation to just dive in.
In addition to Recuva, there are many other undelete, and file/photo/video recovery programs available. Most are commercial and require money to do perform an actual recovery. However, of all the commercial products I've tried, Recuva seems to work just as well in most all cases, and is the best *free* data recovery software I've used.
Here is a list of various programs I've tried.
001micron Rescue Photo 22.214.171.124 (demo)
001micron.com Digital Camera Data Recovery Software (demo)
001micron.com Digital Photo Data Recovery Software (demo)
Advanced Photo Recovery 1.1
AntlerTek Photo Recovery 1.0 (demo)
Asoftech Photo Recovery 2.0 (demo)
C-Photo Recovery 2.32 (demo)
Digital Camera Photo Repair Tool 126.96.36.199 (demo)
Digital Camera Photos Recovery tool 188.8.131.52 (demo)
Digital Photo Recovery 1.15.7
Digital Photo Recovery Undelete 184.108.40.206 (demo)
Digital Photos Rescue Program 220.127.116.11 (demo)
Digital Pictures Rescue 18.104.22.168 (demo)
EASEUS Photo Recovery 2.0.1 (demo)
Easy Photo Recovery 2.5 (demo)
eIMAGE Recovery 3.0 (demo)
EWorld JPEG Recovery v2.0
FlashPhoenix Photo Recovery 2.7 (demo)
Flobo Photo Digital Recovery (demo)
Hetman Photo Recovery 2.1.5 (demo)
JPEG Recovery Professional 3 - commercial
Ontrack EasyRecovery Professional v6.12.02 - Retail
PANTERASoft JPG Recovery 1.4 (demo)
Photo Recovery Genius 1.2 (demo)
PicaJet Photo Recovery 22.214.171.124 (demo)
RAW Recovery with PANTERASoft (demo)
Recover Corrupted Photos 126.96.36.199
RecoverPlus Pro - commercial
SoftAmbulance Photo Undelete 2.14 (demo)
Thinstalled Easy Photo Recovery 1.3.3
Zero Assumption Digital Image Recovery 1.0
Of the commercial software I've tried, Easy Photo Recovery 2.5 (the version at the time) provided the most effective and thorough recovery of both photos and video from formatted or corrupt SD cards, or recovering an accidentally deleted image or video. I would recommend you us both to recover your data if Recuva somehow doesn't take care of the entire process, other commercial software can do a raw search the card for fragments of photos and attempt to piece them together, in the event of a very corrupt card. And fragments of photos are still better than losing the entire photo, as it may contain the part of the image that is most important.