Step-by-step guide how to setup Drush on a Bluehost account (it's probably very similar on other hosts).

You find links to the detailed explanation of the used commands (non-Drush). Reading those gives you a more solid understanding of the options available with the most used commands, preparing you for a successful continued use of the command prompt.

Get SSH/shell access:

• Bluehost doesn't proviide the needed shell access by default, but does give it quick and easy at request.. Apply fo SSH (shell) access through the cPanel Security  section. You need a scan of a photo ID of the account holder. The times I applied for it, I got a reply in less than ten minutes, telling me the host name to use is the main domain name, the username the same 8-digit user from the account with the usual account password. At least no new things to remember.
• Download and install PuTTY, a free SSH client to access your account (see also Wikipedia). I used the Windows installer. If you are on another Operating System you probably won't need PuTTY. Mac users can go here. Linux users here. 
• Once installed, start PuTTY. In the dialog box, at Host Name, enter:  
  yourwebsite.com  
  Press the ‘Open’ button at the bottom of the dialog box, and PuTTY will connect you to the server. 
• The black command prompt box should open where you can now login with the 8-digit username and the usual password of your account. You won't see anything when you type in the password. Not even the usual dots or asterisks. This is normal.
• You get a short message (usually the last login date) and the command prompt in the form username@yourwebsite.com [~]# . You are in the root of your account.
• If your connection gets aborted due to errors, after you see the PuTTY window stating (inactive), just right-click on it and choose Restart Session. This is quit common to happen, bothering but harmless. You can make your connection more stable:
  • Go to the category Connection of the PuTTY Configuration
  • Set the seconds between keepalives on 40 sec (you can alter it if you like)
  • Type in your Host Name in the Session settings
  • Save the session with a logical name (e.g. keepalive40sec)
  • See also here.

Download Drush:

• You can now experience right away the biggest advantage of working from the command line on your server. Instead of downloading a file to your local machine and uploading it on the server, you now are acting from the server, making uploading obsolete. Type:   
  wget http://ftp.drupal.org/files/projects/drush-6.x-3.3.tar.gz 
  This will download Drush version 3.3 to the root of your server (the recommended place to extract it). You should get a response with the last line saying something like: 00:09:22 (403.96 KB/s) - `drush-6.x-3.3.tar.gz' saved [174892/174892].
  Explanation of the wget command.
• You might want to check if this is still the latest stable version available at the Drush project page. If not, put your mouse on the more recent download link, right-click, choose Copy link address from the context menu and replace the address mentioned above (obviously also in the next step that follows below).

Extract the tar file, check and cleanup:

• Type the TAPE ARCHIVE command (Sure we don't use tapes anymore, but the name is still such. An inheritance of the past.): 
  tar -xvzf drush-6.x-3.3.tar.gz 
  You should get a response with the last line saying something like: drush/LICENSE.txt.
  Explanation of the tar command (TAPE ARCHIVE).
• You unzipped in an auto created directory named drush. Check it typing the LIST command:   
  ls
  It shows you everything in the root directory, including the newly auto created drush/ folder and the original tar file right under it.
  Explanation of the ls command (LIST).
• Don't leave any unused files in the root. Remove it now by typing the REMOVE command:   
  rm drush-6.x-3.3.tar.gz 
  Explanation of the rm command (REMOVE).

Find your exact path and following the instructions in the README.txt included in Drush:

• In many instructions you find a path in the form /path/to/some/folder/ simply because the name of those folders varies from case to case. To find out the exact path of the root of your account, type the PRINT WORKING DIRECTORY command:   
  pwd  
  In the following steps, replace /path/to with the outcome of the pwd command, probably something like /home1/username. 
  Explanation of the pwd command (PATH WORKING DIRECTORY).
• Make the 'drush' command executable. Type the CHANGE MODE command:  
  chmod u+x /path/to/drush/drush  
  In my specific case it was chmod u+x /home4/sharmweb/drush/drush. If  everything went right, you shouldn't see any error messages.
  Explanation of the chmod command (CHANGE MODE).
• Optional, but recommended, create a link to drush in a directory that is in your PATH. Type the LINK command:   
  ln -s /path/to/drush/drush /path/to/bin/drush  
  In my specific case it was ln -s /home4/sharmweb/drush/drush /home4/sharmweb/bin/drush.
  Explanation of the ln command (LINK).
• You're done! Try if it works by typing your first and most useful drush command:  
  drush help  
  It outputs a list of all available commands. Read it. You can even  view only the help of a specific command. Try:  
  drush help dl 
  Note how the actual help text for this specific command is now a lot more specific too and dl is an abbreviated alias of the command pm-download 

An extra exercise to make it complete:

• Say you want to see the README.txt of Drush on your server, just to check if the above instructions were right. First you have to go to the right folder /drush. Type the CHANGE DIRECTORY command followed by the directory you want to goto:   
  cd drush 
  Explanation of the cd command (CHANGE DIRECTORY).
• Use the LIST command ls (see above) again just to visualize the files available. Note the presence of README.txt.
• Now to open the file to read the content we need a simple built-in text editor like vi which stands for VISUALIZE. Type:  
  vi README.txt  
  Note that filenames are case sensitive . The command to quit VI without saving is  
  :q!   
  (yes, with the punctuation mark in front). It might be a bit confusing to see where your cursor is.
  A user manual of the vi editor (VISUALIZE).
• Close PuTTY, type:  
  exit 

The usage of the command line doesn't stop here. There are many other interesting Unix and Drush commands coming handy as you progress in Drupal. Like diff (http://en.wikipedia.org/wiki/Diff) and cvs update (http://linuxdevcenter.com/pub/a/linux/2002/01/03/cvs_intro.html) to roll patches. But that will be for some other time. Meanwhile, have fun.

Credits:
This article is the textual explanation of a section in this screencast. Recommended to watch anyway,  but a "must" if you're on another host than Bluehost or you want to deploy a new drupal site from the command line (much quicker than going through your local machine).

Note:
PuTTY's copy and paste works entirely with the mouse. In order to copy text to the clipboard, you just click the left mouse button in the terminal window, and drag to select text. When you let go of the button, the text is automatically copied to the clipboard. You do not need to press Ctrl-C. When you click the right mouse button, PuTTY will read whatever is in the Windows clipboard and paste it into your session instantly, without the usual context menu appearing.

Troubleshooting:
If some drush commands work and other don't, follow the rest of the instructions in the README.txt of Drush. This is likely to happen in a multi-site environment.

If you get "Fatal error: Allowed memory size ..." messages, create a php.ini file in the drush directory with:

Then use the following alias in .bash_profile in the user root directory then restart a bash session.

alias drush='php -c /path/to/php.ini /path/to/drush.php'

In my case it was:

alias drush='php -c /drush/php.ini /drush/drush.php'

See also http://drupal.org/node/186315.