map{print"$_ is married to $couples{$_}".chr 10}sort keys%couples}

or:

map{print"$_ is married to $couples{$_}<br>"}sort keys%couples}

The latter, of course, only newlines in HTML.

Update: print"$_ is married to $couples{$_}<br>"for sort keys%couples :)