Long story short, my laptop was stolen, and I reacquired it a few days later to discover that Windows 8 had been installed over my Debian system. There was much emotionally important data on the HDD, and I'm looking to recover as much of it as possible. I have made an image of the drive to work with and have been researching how to use TestDisk, PhotoRec, and/or Foremost on it, but I'm unsure exactly how to proceed given my specific situation. The drive partition structure was totally changed during the Windows install, and I can't find much info on what to do in such a case.

Running testdisk on the image finds two current NTFS partitions, one bootable and one primary. Quick Search finds the Linux partitions that existed before the repartitioning/reformatting (a parimary bootable and a swap partition). I assume this is a good thing. But how should I proceed from here?

Any help appreciated. I have also made a thread on the cgsecurity.org forums, but it's taking forever to be approved and I thought I might have more luck here anyway.

Testdisk will be of no use in your case, since the filesystem(s) on that disk will be destroyed due to the overwrite with Windows. You will have to use Photorec (I wouldn't recommend Foremost, it wasn't updated in about 5 years).
Use it on the image-file and let it search in the free space of the partitions. You may want to narrow down the search to the specific file formats in the File Opt menu, this will decrease runtime and the number of unneeded files. Since Photorec is a brute force file carving tool this will nonetheless take some time, it may be a good idea to use that time to think about a good backup strategy to prevent incidents like that in the future.

Oh trust me, I've taken a good lesson from this.

But about using PhotoRec, I'm not sure I understand. You're saying I should just go ahead and search the free space of the current NTFS partitions? There's an option to use the whole disk instead. Should I do that instead? Or does it matter? Does the partition structure even matter at this point?

Using the whole disk does not make much sense, those parts that are not marked as free only contain parts of the Windows system and you surely don't want to recover that. Concentrating on the free space, those parts that are not overwritten by Windows anyway, will reduce the time for the recovery action and, more important, reduce the amount of found files that are useless.
The largest part of a recovery job with low-level file carvers like Photorec isn't the actual file carving, but you sitting down and looking through all the found files, sorting the good from the useless. I have done some of those recovery actions for friends (all of them bought external harddisks for backups immediately afterwards) and the results were astonishing. People who had about two thousand photos on their harddisk had to find them between 60.000 images that were carved from the disk. Keep in mind that low level carvers in most cases will not recover filenames. So while with a good file manager you can take a look at the thumbnails of those images to get a first impression which may be useful and which not, I also had a friend for whom I had to restore a MP3 collection. Imagine playing thousands of MP3s to find those you are interested in.
Believe me, you will keep the ratio of important files/found files as high as possible, by all means. So, don't include parts of the disk that can't hold your files anyway (because they are overwritten), use the File Opt menu to only search for files that you know are relevant, and so on. If you happen to search for more common formats, like PNG, JPG or even plain text files, you will literally get thousands of files to search through.