What does "rm is hashed" mean?

It's a performance thing; instead of searching the whole path for the binary every time it is called, it's put into a hash table for quicker lookup. So any binary that's already in this hash table, is hashed. If you move binaries around when they're already hashed, it will still try to call them in their old location.

See also help hash, or man bash and search for hash under builtin commands there.

As others have mentioned the hash is a associative array (key --> value) that Bash maintains so that when a command is executed, Bash searches this hash first to see if the command's location on disk has already been found via $PATH, and stored there for quicker searching.

You can preload the hash by giving a list of commands that you want Bash to find when it's invoked. This variable is called BASH_CMDS.

excerpt from man page

   BASH_CMDS
          An  associative  array  variable  whose members correspond to the 
          internal hash table of commands as maintained by the hash builtin.
          Elements added to this array appear in the hash table; unsetting 
          array elements cause commands to be removed from the hash table.

Additionally if you look at the Bash man page there is a section titled, COMMAND EXECUTION which details the state machine that Bash uses when a command is typed at the prompt.

excerpt

   If the name is neither a shell function nor a builtin, and contains no 
   slashes, bash searches each element of the PATH for a directory con‐
   taining an executable file by that name.  Bash uses a hash table to 
   remember the full pathnames of executable files (see hash  under  SHELL
   BUILTIN COMMANDS below).  A full search of the directories in PATH is 
   performed only if the command is not found in the hash table.  If the
   search is unsuccessful, the shell searches for a defined shell function 
   named command_not_found_handle.  If that  function  exists,  it  is
   invoked  with  the  original command and the original command's arguments 
   as its arguments, and the function's exit status becomes the exit
   status of the shell.  If that function is not defined, the shell prints 
   an error message and returns an exit status of 127.

You can find out what's currently in your hash using the -l switch.

Example

$ hash -l
builtin hash -p /usr/bin/rm rm
builtin hash -p /usr/bin/sudo sudo
builtin hash -p /usr/bin/man man
builtin hash -p /usr/bin/ls ls

hash is a Bash shell built-in that provides hashing for commands.

hash [-lr] [-p filename] [-dt] [name]

Straight from the horse's mouth:

help hash

Remember or display program locations.

info Bash → Shell Builtin Commands → Bourne Shell Builtins

Remember the full pathnames of commands specified as NAME arguments, so they need not be searched for on subsequent invocations. The commands are found by searching through the directories listed in $PATH. The -p option inhibits the path search, and FILENAME is used as the location of NAME. The -r option causes the shell to forget all remembered locations. The -d option causes the shell to forget the remembered location of each NAME. If the -t option is supplied, the full pathname to which each NAME corresponds is printed. If multiple NAME arguments are supplied with -t the NAME is printed before the hashed full pathname. The -l option causes output to be displayed in a format that may be reused as input. If no arguments are given, or if only -l is supplied, information about remembered commands is printed. The return status is zero unless a NAME is not found or an invalid option is supplied.