Hat Yai is a city in southern Thailand.
When walking from the train station follow Tamnoonwithi Rd, continue out of the city and then walk over a bigger rd. Turn right on the next bigger road which should have signs for Sadao (a town south). It is not difficult, you can always ask local "Malaysia?" and point to both directions and see what they say. When walking down the highway (its just a big road) I got a lift just before the road turned into a proper highway out. When you enter Malaysia you are only allowed to hitchhike at toll stations or rest stops.