Aside from version control tools such as cvs or svn, perl, and of course the standard GNU utils (coreutils and binutils), I would choose:
ssh: A must have. One feature i cant live without are tunnels.
vim: I need an editor and like this one. And no, i have never tried emacs.
screen: Incredibly useful when you need to deal with multiple terminals, but you dont want to switch between lots of windows, tabs or consoles.
zsh: Offers lots of useful features that other shells does not.
sed and awk: Yes, Perl does it, but usually i do it faster whith this.