Let me start by saying that I've never been, but a couple of thoughts Ideas to help you get started:
- Find out the current country the villages/towns are located in. This can make a huge difference. Parts of what might have been referred to as 'Hungary' can easily now be part of Czech, or Ukraine as well. Regardless of where you fly into, the borders might be tricky to negotiate. Also bear in mind that the name your father knows the city by, might not be a common name -i.e. Munkac is better known as Munkachevo.
- If there are no relatives or family who can give you more insight, you may want to try to reach out to some of the organizations that fund programs there to help you find people that can help. The Joint (aka The American Joint Distribution Committee, JDC) funds a lot of programming in that area, as do some of the local Jewish Federations, you may want to call them up, and ask if they can help you find someone who can help you (I doubt that they have the info or resources to help you directly).
- Kevarim might be hard to find, because of vandalism and anti-semitism. As an Example, my wife's family immigrated to the US in the 70's. Her father knew where the cemetery was, but his father would never allow him to walk in to the cemetery because of Ayin Hara - so he had no idea where his family's graves were. When he went back in the 90's, most of the headstones had been damaged, and the graves were hard to find. Again, the Joint funds programs to repair and maintain some of these cemeteries, so they might have a person who can help you.
I hope this helps.