Say sudo -K, then retry your test. If it starts asking again, all that was happening is that you had sudo configured to remember your password for some time.
On top of this, Ubuntu's default sudo configuration makes it remember your credentials across ttys. This affects ssh sessions, as you've discovered, since each new ssh connection looks like a new terminal to the low-level OS code.
This also affects things like the graphical Terminal app. If you authenticate with sudo, then create a new tab with Ctrl-Shift-T, you'll find that you don't need to give a password to sudo again in that tab, despite the fact that it also creates a new tty. You can even close the Terminal app entirely, and as long as you restart it within the normal password timeout, sudo will run without requiring you to re-enter your password. This behavior may be enough to make you decide you want to keep this feature enabled.
Mac OS X works this way these days, too.
Not all *ixes do. Red Hat Enterprise Linux (and derivatives like CentOS) insist on getting the password on each new tty.
You can disable both behaviors by changing the Defaults line in /etc/sudoers to something like this:
Defaults=env_reset,timestamp_timeout=0,tty_tickets
The env_reset bit should be there already, and isn't relevant here
The timestamp_timeout directive tells it to immediately time out each sudo session. It's like saying sudo -K after every normal sudo command.
The tty_tickets directive ensures that it associates credentials with the tty they were used on, not just the user name. This is supposed to be the default already, and is documented as such on Ubuntu, but they must have built their distribution of sudo to disable this option, for the convenience reasons given above.
sudo cmdinstead of justcmd. But nowsudo cmddoes not ask me for password any more.