Устанавливаем apt-zip:
apt-get install apt-zip

В /etc/apt/apt-zip.conf определяем носитель для переноса пакетов между машинами.
Например, меняем "MEDIUM=/media/zip" на "MEDIUM=/media/disk"

Обновляем кеш пакетов:
apt-get update

Записываем на Flash диск примонтированный как /media/disk список пакетов для обновления:

apt-zip-list

На Flash будет записан shell скрипт (fetch-script-wget-имя_машины ) для загрузки пакетов
при помощи утилиты wget. На машине с высокоскоростным линком достаточно просто запустить этот скрипт.

Тип обновления задается в /etc/apt/apt-zip.conf через переменную DEFAULT_APTGETACTION:

upgrade - обновление уже установленных пакетов из репозиториев, определенных в /etc/apt/sources.list
dselect-upgrade - от upgrade отличается использованием dselect
dist-upgrade - поддерживает расширенный разрешения конфликтов, больше подходит для выполнения обновления
всего дистрибутива до более новой версии.

После того как необходимые пакеты будут скопированы на Flash, на машине на которой
нужно произвести обновление необходимо выполнить:

apt-zip-inst

Для запроса установки новых дополнительных пакетов можно использовать:

apt-zip-list -a upgrade -p openoffice.org,digikam
...
apt-zip-inst -a upgrade -p openoffice.org,digikam

--------------

Рекомендации от _selivan_. Если дома есть dial-up, создаем скрипт upd.sh:

#!/bin/bash
# Usage: get_soft_links.sh ...
URLS=soft`date +%F_%H.%M`-urls.txt
LIST=soft`date +%F_%H.%M`-list.txt
DIR=~/links
# get links
apt-get --print-uris -y -qq dist-upgrade | cut -d' -f2 > $DIR/$URLS
apt-get --print-uris -y -qq install $@ | cut -d' -f2 >> $DIR/$URLS
# print names of requested packages to file
echo $@ > $DIR/$LIST
#convert unix newline format to windows for windows download managers
sed -i -e 's/$/r/' $DIR/$URLS

Если диалапа нет - на один шаг больше:

apt-get --print-uris update
...

--------------

Рекомендации от sHaggY_caT по использованию yumdownloader в Fedora, Centos, ASP и других Red Hat-подобных дистрибутивах:

Ставим yum-utils.
Для генерации листа закачки можно использовать скрипт
(первый аргумент название пакета, второй, имя выходного файла):

#!/bin/sh
yumdownloader --urls $1 | sed '1,2d' > /media/disk/$2.txt

Удаление первых двух строк поставлено, так как там служебная информация от плагинов и yum.
К сожалению, yum не разделяет вывод служебной информации и результат на потоки, по этому, сделать 2>/dev/null нельзя

Что касается машины совсем без интернета, в тут возможность подобная "apt-get --print-uris update" не получится.
Можно только сгенерировать список для загрузки с ключем "-C":

yumdownloader -C --urls пакет

Преварительно нужно все-таки обновить кэш с помощью "yum update".

В основанных на Red Hat дистрибутивах скаченные пакеты можно либо с помощью yum либо с помощью rpm:

yum localinstall название_файлов_пакетов_через_пробел
rpm -Uhv название_файлов_пакетов_через_пробел

Yum скачает недостающие зависимости. Если список был сгенерирован верно, то это не нужно,
и необходимо использовать rpm.

Две полезные команды, которые установят все rpm-пакеты из текущей директории:

ls -l | grep rpm | awk '{print $9}' | xargs yum localinstall
ls -l | grep rpm | awk '{print $9}' | xargs rpm -Uhv

--------------

Как заставить apt-get установить вручную загруженные пакеты: http://www.opennet.ru/tips/info/1707.shtml

Для загрузки обновлений на внешней машине с Windows можно использовать Keryx
(http://www.opennet.ru/opennews/art.shtml?num=19650)

В графическом интерфейсе synaptic есть возможность сгенерировать скрипт для загрузки выбранных пакетов
с их последующей установкой: "генерировать скрипт закачки пакетов" и "добавить закаченные пакеты".