/usr/local/bin needs to be a part of your PATH. Which is very strange because /usr/local/bin is almost automatically part of your PATH.
Here's a little more explanation:
Your PATH is a list of directories that hold your executables which means, as you said, you can go anywhere on your system and execute the commands in these directories without the full path. To add /usr/local/bin to your path, do the following:
QUOTE
export PATH=$PATH:/usr/local/bin
You should add the above line to your ~/.bashrc file so that /usr/local/bin gets added to your path at each login.