Abra o terminal e execute:
wget -c http://valgrind.org/downloads/valgrind-3.6.1.tar.bz2
ou se você quiser, pode baixar e também extrair o valgrind-3.6.1.tar.bz2 usando curl com este comando:
curl http://valgrind.org/downloads/valgrind-3.6.1.tar.bz2 | tar jx