Receovering Lost Files

I've heard that nothing is every really deleted in a computer, and I had a video clip from a few years back of me and my friend tearing around on a go-kart we built, ok it was a bit of scaffolding with an engine and a seat but it was great fun. Anyhow over the years I've most likely deleted the video clip and now I really would like to recover it but have no idea if that is even possible. Any help would be great. 
