Using md5deep
md5deep -r path/to/dir > sums.md5
Using find and md5sum
find relative/path/to/dir -type f -exec md5sum {} + > sums.md5
Be aware, that when you run check on your MD5 sums with md5sum -c sums.md5, you need to run it from the same directory from which you generated sums.md5 file. This is because find outputs paths that are relative to your current location, which are then put into sums.md5 file.
If this is a problem you can make relative/path/to/dir absolute (e.g. by puting $PWD/ in front of your path). This way you can run check on sums.md5 from any location. Disadvantage is, that now sums.md5 contains absolute paths, which makes it bigger.
Fully featured function using find and md5sum
You can put this function to your .bashrc file (located in your $HOME directory):
function md5sums {
  if [ "$#" -lt 1 ]; then
    echo -e "At least one parameter is expected\n" \
            "Usage: md5sums [OPTIONS] dir"
  else
    local OUTPUT="checksums.md5"
    local CHECK=false
    local MD5SUM_OPTIONS=""
    while [[ $# > 1 ]]; do
      local key="$1"
      case $key in
        -c|--check)
          CHECK=true
          ;;
        -o|--output)
          OUTPUT=$2
          shift
          ;;
        *)
          MD5SUM_OPTIONS="$MD5SUM_OPTIONS $1"
          ;;
      esac
      shift
    done
    local DIR=$1 
    if [ -d "$DIR" ]; then  # if $DIR directory exists
      cd $DIR  # change to $DIR directory
      if [ "$CHECK" = true ]; then  # if -c or --check option specified
        md5sum --check $MD5SUM_OPTIONS $OUTPUT  # check MD5 sums in $OUTPUT file
      else                          # else
        find . -type f ! -name "$OUTPUT" -exec md5sum $MD5SUM_OPTIONS {} + > $OUTPUT  # Calculate MD5 sums for files in current directory and subdirectories excluding $OUTPUT file and save result in $OUTPUT file
      fi
      cd - > /dev/null  # change to previous directory
    else
      cd $DIR  # if $DIR doesn't exists, change to it to generate localized error message
    fi
  fi
}
After you run source ~/.bashrc, you can use md5sums like normal command:
md5sums path/to/dir
will generate checksums.md5 file in path/to/dir directory, containing MD5 sums of all files in this directory and subdirectories. Use:
md5sums -c path/to/dir
to check sums from path/to/dir/checksums.md5 file.
Note that path/to/dir can be relative or absolute, md5sums will work fine either way. Resulting checksums.md5 file always contains paths relative to path/to/dir.
You can use different file name then default checksums.md5 by supplying -o or --output option. All options, other then -c, --check, -o and --output are passed to md5sum.
First half of md5sums function definition is responsible for parsing options. See this answer for more information about it. Second half contains explanatory comments.