AC Current Sensor to detect treadmill usage
Non-Invasive Current Sensor - 30A
&lt;== This thing would probably work well. It doesn't need to connect to your treadmill directly. It uses inductance to detect current flow. You don't have to use an Arduino, but it would be one of the easiest ways. 

There are many wireless things you could do: XBee, WiFi, Bluetooth, etc. All of them are somewhat expensive $80-200 range. Logging data to a MicroSD might be an easier solution.