After making a selection in a layer, right click on it and choose save selection as.
Update for QGIS 3.2 Bonn as of 2018
As this is the accepted answer and the way of doing this has evolved somewhat, beginners might find this answer incomplete, so:
After making a selection in a layer, right click on it and choose "Export" > "Save Selected Feature As..."
which is actually just a nice redundancy, because it takes you to the same mask as clicking "Save Feature As...", but it already checks the box "Save only selected features"
