Зависит от приложения. Если говорить о конфигурации (для mysql это /etc/mysql/my.conf если не ошибаюсь) то её purge удалит. Если говорить о содержимом БД то его было бы немного некорректно удалять автоматически. Например, я ставил MariaDB - она по зависимостях удаляет MySQL, но подхватывает её БД. Я бы был сильно удивлен, если бы обнаружил пропажу баз и таблиц при таком обновлении.
Основная масса таких файлов (хотя это весьма редкое явление) лежит в /var/lib и /usr/share (судя по моим наблюдениям). Так же можете сделать поиск по файловой системе с названием пакета.
Второе - это конфигурация пользователя. Например, если вы удалите браузер, или оконный менеджер - их настройки останутся в домашней папке пользователя, хотя в остальной части системы будет число. Обычно такие настройки лежат в:
~/
~/.config
~/.local/share
Можете просмотреть там и удалит ненужное. В худшем случае приложение загрузится с настройками по умолчанию (только не трогайте папки типа .gnugpg, .ssh, .pki и прочее что может быть связано с входом в аккаунт и подобным, удаляйте только те названия, о которых знаете что это).
Третье - это gconf/dconf хранилища настроек - что-то типа реестра в Windows. Удаление разделов только через терминал, при желании можно пользоваться.
Ну и последнее - когда ставите пакеты - перечисляйте минимальный набор пакетов. Например, если вам нужен веб-сервер с Apache2, PHP и MySQL - проще всего сначала поставить mysql-server, а потом PhpMyAdmin, который потянет за собой все нужные зависимости (или вручную mysql-client apache2 php5). Рекомендую использовать synaptic - выбрав пакет для установки получите список того, что устанавливается по зависимостях, возможно одного пакета будет достаточно (например часто советуют ставить пакеты nvidia-current nvidia-settings, когда первого достаточно, он потянет второй по зависимостях). В таком случае когда вы снесете пакет - все зависимости будут предлагаться для удаления автоматически, а когда вы вводите список пакетов в три строчки - для чистоты придется смотреть и удалять все по очереди вручную, иначе они будут стоять вечно, ибо установленные вручную и вроде как нужны кому-то. Ещё иногда ставятся пакеты которые рекомендуются, они после удаления могут не предлагаться для удаления; отказаться от таких пакетов можно так:
apt-get install --no-install-recommends unity
Получилась почти статья, но в целом это всё. Такое использование системы позволяет держать её чистой долгое время в отличии от Windows, где сборка мусора неизбежна. Здесь есть весьма ограниченное количество мест, в которых могут остаться файлы, и их легко найти.
Как пример - моя система обновлялась с 12.04, сейчас уже месяца четыре как стоит 14.04, при чем раз или два делал даунгрейд, например с 14.04 до 13.10, но потом опять обновление до 14.04. При этом система чистая, и быстрая.
А ещё если появляются какие-то проблемы - в 99% их можно решить без переустановки, просто спросите у людей.
