A large number of physical solutions have already been provided, so I would like to give a software one that can, of course, also be used in addition physical measures.
Put some kind of port security up (preferably 802.1X) - while MAC whitelists can be relatively easily circumvented, I'd like to see someone circumvent 802.1X without physically disassembling your lab machines.
Also put up a sign explaining that removing the cables is now only good to make The Sysadmin angry, and that they won't like him when he's angry. (Public display of a LART is highly recommended.)
If you have BOFH inclinations: Make the cables work even for unauthenticated users, but assign them a special IP range. Log access to any authenticated services from said IP range, and lock the user accounts. This way, they'll come to you to pick up their punishment, and you don't need to constantly watch the logs and immediately sprint to the correct location for catching the person (you still may want to do that for the added "all-seeing admin" effect). Or just redirect everything to a login form, and connect it to a "lock account on correct login" script. You will be amazed how many users are dumb enough to try. (Originally, I wanted to suggest simply blacklisting their MAC so their laptop doesn't work anywhere on the network, but since MACs can be faked so easily, this could both be easily circumvented and lead to nasty pranks.)
If you are nice and want to provide cable-based access: Do what my university did, add a second NIC, add a 1.5m network cable to it, and route/bridge/whatever it to the network. (All cables behind the PC go through a giant zip-tie to make stealing cables, mice etc. harder.) In my university, the users have to log in on the PC and activate said cable there, making sure only authenticated users can use it and all access can be attributed to a user. Unplugging the "uplink" cable from the PC and accessing it directly is prevented by 802.1X, as far as I know.