Ajax+ PHP Map

I have a client who wants to add some searching capabilities to their site. We want the searches to be cool so need to somehow provide a map of the state broken down by counties and allow people to search for items within that certain county. I wanted to do something cool with Ajax and PHP but really don't know where to start. I have looked at Yahoo and Google maps but I don't need to map to the street level, just a county breakdown...does anyone know of an app that could create a map for me? Do I need to start from scratch and get out photoshop or fireworks and actually try to draw a map? Does anyone know of anything like this online? Thanks!