Pasting with the middle-button has been standard way to paste on Unix systems for ages. And I haven't had a mouse with a middle button for ages. Yes, the wheel can be pressed which acts as a middle-button, but it sucks as a button. So far the best copy/paste system for a terminal that I've seen is in Putty in Windows: selecting text automatically copies it to the clipboard and right button pastes.
I use Ubuntu a lot and I've been otherwise happy with Ubuntu's gnome-terminal, so I implemented above mentioned copy/paste system to gnome-terminal to make my life easier.
Here's the patch for gnome-terminal: right-button-paste.patch
It was made against Ubuntu 11.04 current gnome-terminal, but it should apply easily to older versions also.
Here are simple instructions to apply the patch and compile gnome-terminal. I'm not that familiar with debian build system, so the instructions may not be as elegant as they could be.
Install build dependencies
sudo apt-get build-dep gnome-terminal
Download the sources and apply the patch
mkdir gnome-terminal cd gnome-terminal apt-get source gnome-terminal cd gnome-terminal-2.32.1 patch -p1 < path/to/right-button-paste.patch
Build
dpkg-buildpackage -us -uc -b
Install
cd .. dpkg -i *.deb