You paste into NetHack with the usual means of your operating system. For example, in OS X, you paste using Command + v into the respective popup opened by the tiles port, or using Command + v into the terminal window you telneted to NAO with. A terminal application such as putty may also offer paste in its menus. xterm as well as most xterm based terminal emulators allow you to paste using shift + insert. With the tiles port, you can only paste whenever the game prompts you, e. g. what to engrave or wish for.
This is useful with Elbereth. Users of GNU screen can put this in their screenrc to make control-E engrave it in the dust:
bindkey "\005" stuff "E- Elbereth^j"
Users of tmux can put this in their .tmux.conf to make Control-E engrave it in the dust:
bind-key -n C-e send-keys "E- Elbereth" C-m
Beware, pasting junk you accidentally left in the clipboard into the tty port often results in Yet Another Stupid Death. Another hazard is IP packet loss if you are playing online and paste large chunks. Unrelated but similar in effect is an unreported bug where NetHack will occasionally behave as if large portions of random text were pasted into its input stream (observed on OS X with both NAO and tiles port).
See also: bot