I have a Nexus 4 and tether it just fine. I use bluetooth but I have also tried WiFi hotspots and that works as well, but I feel that the bluetooth is more stable.
I don't use any kind of software as it just connects by enabling bluetooth tethering in the settings menu. On my N7, I have a tasker widget so I can just tap it and it connects directly to the N4 without having to go through the menus.