I can see room for several questions and answers:
A: Software. Sure, this is a moving target, but softwarerecs doesn't work. This answer should distinguish between programs that attempt to recover data, and ones that try to rebuild the partition table. Splitting the answers between platforms -- Mac, BSD, Linux, Windows
B: Hints. This is a set of answers about signature values that can be searched for with a disk editor to try to determine the original layout of the disk. E.g. is the first sector of an HFSJ+ partition unique?
C: Resources. Links to other web pages that may help.
Also, this is not just a linux question, but is common to many operating systems. Such a canonical set of answers should be on an exchange that spans operating systems. Superuser?