Probably the easiest way to do it would be to use the phone as WiFi hotspot. Not sure if the Galaxy Europa can do that out of the box, you might need to install an app. That's what I'm doing as I write this post, tethering my Linux laptop to my Android phone via WiFi. BTW I'm using Linux Mint as well.
Samsung Kies is proprietary Windows software, so not quite sure how tethering works with that anyway. I've never used it, when I had a Samsung Galaxy phone.