Восстановление возможно, если поверх отформатированной области не было записано чего-либо нового. Если это произошло — сделать ничего нельзя. В моём случае ситуация была осложнена тем, что на компьютере не было рабочей ОС.
Введение

Имеем: нерабочие ОС и/или отформатированный диск, желание не потерять файлы.
Понадобится:

несколько часов времени,
Live CD (любой удобный для вас Linux, в данном случае использовался Ubuntu 11.10),
дисковод,
интернет.

У меня стояли две ОС: Windows 7 и Ubuntu 11.10. Винда что-то перестала загружаться, и я решил восстановить систему. Делалось это стандартными средствами, и я выбрал пункт «Восстановление системы до первоначального состояния», что было ошибкой. Ведь первоначально Ubuntu на компьютере не было, и программа восстановления отформатировала весь жёсткий диск перед тем, как переустанавливать Windows. Мне было предложено перезагрузить компьютер, после чего появилась зловещая белая надпись на чёрном фоне
grub resque>

и не грузилась ни одна ОС. Это было печально. И, чтобы восстановить файлы, Костик меня научил следующему. После я проделал это самостоятельно для лучшего запоминания и решил написать инструкцию. Итак, приступим.
Установка testdisk
Записываем Live-CD c Linux (в моём случае это была Ubuntu 11.10 64-bit) и загружаемся с него. Открываем терминал и устанавливаем программу testdisk:
sudo apt-get install testdisk

Запускаем её с правами root, чтобы можно было видеть все подключённые носители информации:
sudo testdisk

Работа с testdisk
Создать новый log-файл
Далее будем работать в этой программе. Выбирайте Create (Создать новый log-файл):

Жмёте continue:

Выбрать архитектуру
Выбираете вашу архитектуру (обычно это будет Intel, если у вас не Mac или что-либо перечисленное):

Анализ структуры диска
Выбираете пункт Analyse:

Быстрый поиск
Затем Quick search:

Выбираете раздел, на котором хранятся необходимые файлы:

Глубокий поиск
Если разделы не найдены, как было у меня, запускаете Deeper search (очень долгая операция, заняла около 50 минут):

Ждёте, пока программа ищет все данные о существовавших на этом жёстком диске разделах:

Выбираете, наконец, нужный пункт:

В моём случае был выбран последний пункт из спинно-мозговых соображений. Размер у последнего Линукса чуть больше, т.к. предположительно программа восстановления отрезала необходимое ей место (т.к. с момента покупки диск переразбивался на разделы, а программе восстановления всё хотелось видеть в первозданном виде). Подумайте, что именно вам нужно. Возможно, что более чем один пункт будет пригоден. Появится что-то подобное:

Копирование найденных файлов
Выбираете нужный раздел и нажимаете кнопку P, чтобы перейти к списку файлов. Я выбирал Linux. Выглядит это примерно так:

Перемещайтесь по папкам с помощью стрелочек вправо и влево. Выбирайте нужные файлы и копируйте их кнопкой «c». У меня они копировались в/home/user, а оттуда с помощью обычного файлового менеджера я их перемещал куда-нибудь. При копировании будьте внимательны, некоторые файлы иногда записываются неправильно, сразу проверяйте.
Вот и всё. Удачного восстановления!
P.S. После спасения своих файлов я поставил Ubuntu заново, она переставила grub2 куда следует, и обе системы стали работать.