You've been spending too much time in the world of Microsoft - where connecting more computers to a network somehow requires extra software.
Since its a USB internet connection, that rather implies that the hardware only supports one computer connection at a time - but most operating systems provide routing support - if configured, they will choose the right interface to forward packets on.
The complication with this is that for domestic internet connections, the service provider usually only assigns a single IP address for your use. So the router has to rewrite the addressing information on the packets. This is generally referred to as NAT (network address translation) or, in the case where a network is exposed as if it were a single host, masquerading. Have a google for (the Linux distribution you use, e.g. Ubuntu) + masquerade
Assuming the internet connection works OK on your Linux box, then the actual hardware / upstream provision is irrelevant.
Note that you can buy masquerading routers off the shelf for less than 50 USD these days - if you're uncomfortable with the idea of tweaking your system this can be a simpler route.