Malacca (Malay: Melaka) is a city in Malaysia. It's very artsy and kind of the hippie central of Malaysia.
North or South towards Kuala Lumpur, Singapore
The motorway is quite far outside the city and the public transport can be unbelievably inefficient. It can easily take 2-3 hours to leave the city. First you have to get to the main bus station, i.e. by the local bus from Dutch Square. From there, find the bus that goes to the Zoo and take it to the last station. You are now on the main road that leaves the city. It's probably possible to hitchhike right from there, but cars are fast and won't know where you are going. It's about a thirty-minute walk to a huge toll gate at the motorway entrance, which makes an excellent hitchhiking spot and you are likely to get a direct lift to KL or the Singaporean border from here. It's also possible to hitch out on the main road by the bus station. One hitcher, with a a big E2 TOLL sign, found a ride within minutes.
If your driver just passes Malacca, have them drop you at the motorway exit, walk to the toll gate and try to find a lift from there as far as possible in direction of the city centre. Going there by bus will take a long time and taxis are expensive.