I've got three ideas for you. They all have their share of complexity and you can mix and match as you see fit. The first is probably the easiest, but least robust (on its own).

1. Passive MAC detection

The standard way would be to keep track of the MAC addresses that are requesting DHCP addresses from the router. Most routers provide an "Attached Devices" style screen that will tell you who's connecting.

This isn't automatic, but you could (fairly easily) script some Bash/Python to pull the router page down, parse out the MAC addresses and check them against a list of known/allowed MAC addresses.

The problem here is nothing is instant. You rely on the router to update its page and you have to poll this frequently. Some routers won't like this. I have a crappy Edimax router that crashes if you load more than 10 pages in a minute (pathetic!) so this might not work.

MAC addresses are also woefully spoofable. macchanger for example, will let you spoof your MAC address in one command. I think even Network Manager will let you do it. If somebody doesn't want to be detected, they'll monitor network traffic and spoof one of the valid (known) devices.

2. Active Sniffing

This is where we rip the wheels off and dig in. You'll need a spare wireless something-or-other in a place that can intercept traffic to/from the router (ideally quite close to it).

In short, you hook up airodump-ng and you watch people connected to your network. It should be possible to script this output so when a new device shows up and starts using your network, you can instantly do something.

The idea would be that you run this on boot (as root):

airmon-ng start wlan0
airodump-ng --bssid 00:1F:9F:14:6F:EB -w output --output-format csv mon0

Replace the BSSID with your access point's.

This writes an auto-incrementing file that can be parsed on a regular basis. The version above write a comma-separated value file which is quite basic but if you're happy with XML (Python can make it pretty simple) you might want to look at the netxml output format for airodump.

Either way, this gives you regular information about which devices are using the network (and how much traffic they're sending too). It's still just as fallible as using the router's ARP table, but it's live.

While you're in promiscuous mode, if your script does pick up a client it thinks shouldn't be on the network, you could use tcpdump to trawl the packets and log exchanges of interest (HTTP requests, etc). It's more programming but it can be done.

3. Fingerprinting with nmap

Another method is to sweep the network for clients with nmap. Normally, you might think, this wouldn't help you too much, if somebody is blocking pings, it might not show up.

I suggest you use this in conjunction with either of the two other methods. 1 will give you the IP address so you can nmap directly. 2 won't give you an IP but it will let you know how many clients nmap should expect to find, at that exact moment in time. Make sure all your devices are pingable.

When nmap runs (eg sudo nmap -O 192.168.1.1/24) it will try to find hosts and then it will do a port-scan on them to work out what they are. Your check-list should include how each of your devices should respond to nmap.

If you want to go one further, you could run a simple server on each of your computers. Just something that accepted a connection and then dropped it. In short: Something for nmap to look for. If it finds it open, it's probably your computer.

4. Secure your network better

You should actually do this first if you're worried. Use WPA2/AES. Never use WEP (cracks in about five minutes).

If you're still worried somebody might find out the key (WPA2 takes a lot of data and computational time to crack), move to a RADIUS model. It's an authentication framework that sets up a one-time key for each user. PITA to set up though.

But which to do..?

If I weren't happy with things, I'd probably manually watch airodump. If I still wasn't happy, I'd start fingerprinting things I saw. Somewhat difficult (by no means impossible) to script though.

The easiest to script is going to be router-scraping with fingerprinting from nmap. Short and simple.

My suggestion, Oli's 1.

If your "attacker" gains access without needing to spoof his mac address, he'll assume you thats theres no way you're monitoring your MAC addresses.

Use your own dhcpd with an event to trigger an email if necessary.

I am going to have to do some research, but if it were me, I would run my own dhcpd on a linux box connected to the router (or use openwrt), and then have it email me if there if a macaddress requests an address whats not on a whitelist.

EDIT: http://linux.die.net/man/5/dhcpd.conf has all the resources you need to get this done. Just create an event to execute a script that will check on a whitelist, if the mac address is not on the whitelist, have it send yourself an email. Also see http://ubuntuforums.org/showthread.php?t=1328967