To paste in Nautilus, look at the top of the window where it says, "File EditView..." Select Edit, and one of the items in the drop-down menu is "paste."