When should I use "nohup", and when should I use "&"?

Nohup makes a program ignore the HUP signal, allowing it to run after current terminal is closed / user logged out. Nohup does not send program to background.
& at the end of command is related to shell job control, allowing user to continue work in current shell session.
Usually nohup and & are combined to launch program which runs after logout of user and allows to continue work at current shell session.

Typically I use & when I want to run in the background a command which will not take long to run, or one where I won't really care if the program is terminated if I am unexpectedly logged out of a session.

xcalc &
rdesktop 1.2.3.4 & 
./this_only_takes_a_few_seconds_but_i_want_my_shell_back.py &

When working over a VPN or a dodgy remote connection, I tend to use nohup for running anything which will take a while to run. When running large data imports on a remote host, for example, you might want to use nohup to ensure that getting disconnected won't have you start over when you reconnect.

nohup ./do_data_load.py mydatafile.txt &

It's also used when a developer doesn't properly daemonize a service, so you have to use nohup to ensure it isn't killed when you log out.

nohup sillyd &

If you happen to forget to use nohup when running something like the last two examples, you can use the bash or zsh builtin disown to the same effect.

$ sillyd &
[1] 12345            # Whoops!
$ disown %1

It's pretty rare to use nohup without &, since you can't really reattach to the nohup'd session if you are logged out. This pretty much eliminates its usefulness for interactive commands. In the case where you have an interactive command you want to persist over sessions or avoid complicated disconnects, you can use screen. The firepower of a fully armed and operational screen session is beyond the scope of this post, so you should check it out in more detail.