How can I random sort lines in a buffer?

Using Bash on GNU/Linux:

Similar to Sean's solution, select the region and then:

C-u M-| shuf

Explanation:

M-| pipes the content of selected region to the bash command shuf. shuf shuffles the lines. The prefix C-u takes the output of shuf and uses it to overwrite the selected region.

randomize-region.el seems to do what you want.

Alternatively, here is sort-lines adapted to this requirement.

I've removed the reverse argument (obviously not relevant here), and simply supplied a 'comparison' function returning a random result to sort-subr.

(defun my-random-sort-lines (beg end)
  "Sort lines in region randomly."
  (interactive "r")
  (save-excursion
    (save-restriction
      (narrow-to-region beg end)
      (goto-char (point-min))
      (let ;; To make `end-of-line' and etc. to ignore fields.
          ((inhibit-field-text-motion t))
        (sort-subr nil 'forward-line 'end-of-line nil nil
                   (lambda (s1 s2) (eq (random 2) 0)))))))

For the original:
M-x find-function RET sort-lines RET