yes, in my experience you need the software installed before you delete the item you want to recover.
basically, when you delete an item the data still remains on the disk, the os just no longer thinks it's data that should be recognized as a file. if that area doesn't get overwritten it can be undeleted, but if it does get overwritten you're generally screwed (as far as consumer products go).
andrew davidoff