I've edited this answer for the additional bash fixes that were released on Monday.
For Ubuntu 12.04, I ran an update, but also had to run the install for bash to get rid of the vulnerability.
root@host:/home/ubuntu# env x='() { :;}; echo vulnerable' bash -c "echo this is a test" vulnerable this is a test
That command shows the system is vulnerable, so run the update.
apt-get update && apt-get -y upgrade
Test again.
root@host:/home/ubuntu# env x='() { :;}; echo vulnerable' bash -c "echo this is a test" vulnerable this is a test
Still vulnerable.
apt-get install -y bash
Test again.
root@host:/home/ubuntu# env x='() { :;}; echo vulnerable' bash -c "echo this is a test" bash: warning: x: ignoring function definition attempt bash: error importing function definition for `x' this is a test
Edit: After the additional patches were released, the output has changed.
root@host:/home/ubuntu# env x='() { :;}; echo vulnerable' bash -c "echo this is a test" this is a test
Yay! Fixed. This should work for other versions, but I haven't tested it beyond 12.04.
Also, runamok's reply below works well, so give him an upvote!