Valgrind in OS X Lion
I'd start with a spotlight search from terminal mdfind valgrind as well as checking your path variable to rule out some simple errors before digging deeper. You will want to ensure you have Release 3.7.0 of valgrind as it's the first that states compatibility with Lion in the release notes.