You will need root access to the phone (for old Android versions, Froyo (Android 2.2) and beyond can do it natively). I agree that most Linux distros will recognize it automatically as soon as you enable USB tethering but there are some distros which will not do the same, in that case you will have to follow the steps given above.