Just my notes for fresh debian installations. Till now i always start from beginning again what packages are needed to compile mplayer etc. This is desktop-based.

# boot a knoppix, grml or other debian-based livecd. Must have debootstrap onboard.
fdisk /dev/hda       # create partitions, at least one for / and one for swap.
cat /proc/partitions # see if partitions come up, if not execute 'partprobe' or reboot
mkfs.ext3 /dev/hda1  # create filesystem
mkswap /dev/hda2     # create swap

mkdir /new
mount /dev/hda1 /new                                            # mount fresh partition
debootstrap --arch=i386 sid /new ftp://ftp.de.debian.org/debian # create fresh debian with arch i386. 
echo 'proc /proc proc defaults 0 0' >/new/etc/fstab
echo '/dev/hda1 / ext3 defaults,errors=remount-ro 0 1' >>/new/etc/fstab
echo '/dev/hda2 none swap swap sw 0 0' >>/new/etc/fstab
mount -t proc none /new/proc
chroot /new

echo 'deb     ftp://ftp.de.debian.org/debian          unstable        main contrib non-free' >/etc/apt/sources.list
echo 'deb http://nightlies.videolan.org/build/sid-i386/arch ./' >>/etc/apt/sources.list
apt-get update
apt-get dist-upgrade
echo 'latern' >/etc/hostname
echo '127.0.0.1 latern localhost' >/etc/hosts
echo "alias ll='ls -al'" >>/etc/profile
echo "export EDITOR=emacs" >>/etc/profile

apt-get install locales console-data console-tools emacs23-nox screen
apt-cache search linux-image                          # what linux-images are there?
apt-get install linux-image-2.6-i686 grub             # thats ok for the 32bit-install on athlon xp 2800+ here
mkdir -p /boot/grub
cp /usr/lib/grub/i386-pc/* /boot/grub
vi /boot/grub/menu.lst
echo '(hd0) /dev/hda' >/boot/grub/device.map
mknod /dev/hda b 3 0; mknod /dev/hda1 b 3 1           # didnt exist in chroot yet, needed by grub
grub # install grub to MBR

apt-get install ssh                                   # ensure basic access to the system via network

reboot # boot fresh system
passwd # set root-pw
vi /etc/network/interfaces # setup networking
/etc/init.d/network restart

apt-get install wmaker wmaker-data x-ttcidfont-conf x11-apps # install windowmaker and some suggestions
apt-get install xdm xfonts-75dpi xfonts-base xfonts-efont-unicode \
   xfonts-scalable xfstt xinit xserver-xorg mesa-utils xutils xserver-xorg-core
# now x is configured, windowmaker comes up after executing 'startx' or run from xdm

apt-get install iceweasel gkrellm xterm lsof less strace sudo
# add user for working, visudo to extend permissions
# add user to groups audio and video

apt-get install mpg123 alsa-oss alsa-tools alsa-utils libasound2-plugins binfmt-support

# kaffeine plugin stuff
apt-get install g++-4.3 gcc-4.3 libxt-dev libxext-dev libpng12-dev libjpeg62-dev libqt3-headers

# mplayer - get sources from mplayerhq.hu
apt-get install libxv-dev libsdl1.2-dev
# if you want to encode videos with mencoder: get the x264 codec, liblame, oggenc, mkvmerge
# extract mplayer-sources, configure/make/make install.

apt-get install apt-spy # creates sources.list based on bandwidth-tests etc.
# japanese input: kinput2-canna kinput2-common kanjidic canna-utils canna sumika
# japanese input: apt-get install uim uim-anthy uim-applet-kde uim-qt uim-qt3 kasumi \
#                    uim-applet-gnome uim-xim uim-gtk2.0 im-switch

# japanese fonts
apt-get install psfontmgr emacs-intl-fonts xpdf ttf-sazanami-mincho \
   ttf-sazanami-gothic xfonts-100dpi-transcoded xfonts-75dpi-transcoded \
   ttf-baekmuk ttf-kochi-gothic ttf-kochi-mincho unifont xfonts-baekmuk \
   xfonts-intl-asian xfonts-intl-chinese xfonts-intl-chinese-big \
   xfonts-intl-japanese xfonts-intl-japanese-big xfonts-marumoji \
   xfonts-shinonome gsfonts-wadalab-common gsfonts-wadalab-gothic \
   gsfonts-wadalab-mincho xfonts-intl-asian xfonts-intl-european \
   xfonts-intl-phonetic ttf-arphic-bkai00mp ttf-arphic-bsmi00lp \
   ttf-arphic-gbsn00lp ttf-arphic-ukai ttf-arphic-uming \
   x-ttcidfont-conf ttf-freefont xfonts-ayu xfonts-efont-unicode \
   xfonts-mplus gsfonts-x11 dvi2ps-fontdata-three hbf-kanji48 \
   xfonts-kaname