I try to keep things as simple as possible, because my experience has been that as soon as one starts to complicate things, they don't work!
99% of the Internet Cafes that I have visited use a wired (Ethernet) connection to hook their own computers up to the Internet. I bring my own laptop in (it has a network card in it) and ask permission to unplug the cable from one of their computers, and plug it into my laptop, whilst paying the same price that I would pay if I used their computer. Most of the time, the operators of the cafe are content with me doing this.
The more recent operating systems (e.g. Windows XP with SP 2) will automatically detect internet connectivity. Sometimes, I need to have a look at the network settings on the cafe's computer, and replicate these settings on my own machine. That is the exception, though, not the rule.
It's helpful if you bring a 2 meter long Ethernet extension cable with you - one that has a female connector on one end, and a male connector on the other end. If you can't easily find such a cable, just get a standard RJ45 cable (it will have male connections on each end), and then get a little 'lesbian' connector (female to female) that you can then stick on one end, to allow you to use the cable as an extension. I have found that very often, the cable that runs into the back of the cafe's computer does not have sufficient slack to reach up to the tabletop where I have put my laptop.