If you got a "permission denied" error, it probably has more to do with the .Xauthority issues (or permissions in general) than pathing. Trying to execute a command which lives in a directory not in your path usually results in a "command not found error" instead of "permission denied".
However, here's how the pathing deal goes:
When a user tries to execute a program at the command prompt, the shell looks for the filename in the directories entered in that user's PATH environment variable. If it doesn't find the file in any those directories, it barfs a "command not found" error. This is how DOS does things as well. Note that for security reasons, the directory you are currently in (".") is not searched unless you explicitly tell the shell to look there by prefixing "./" (no quotes) to the command you type.
To append a new directory to an individual user's path in bash, add the following statement to the .bash_profile file in the user's home directory: PATH= $PATH:new_directory_name
To add a path globally (for all users), put that same line in /etc/profile.
In either case, there needs to be an "export" line somewhere after the PATH line, and it must include the word PATH. It might look something like:
export PATH PS1 USER LOGNAME HOSTNAME
This link gives a little more info if you're interested.
By the way:
A) to find out which directories are in the PATH variable, do:
echo $PATH
B) For the changes to take effect, you'll have to kill and restart the shell (logging out and then back in does this), or source the file you edited with the (duh) source command. For example:
source ~/.bash_profile.