Easiest way using the Ubuntu/Debian package nautilus-image-converter:
sudo apt-get install nautilus-image-converter
Using a Custom Photo Resize Script for the Nautilus File Manager
This context menu script can resize to 3 predefined sizes (more can be added) and it asks to put the resized pics in a folder or rename them. Put the script in ~/.gnome2/nautilus-scripts/ named Create_thumbs. (make it executable using chmod +x ~/.gnome2/nautilus-scripts/Create_thumbs). It needs: imagemagick (so install it first using sudo apt-get install imagemagick).
