This is not the fastest method, but do a Google search on the county name followed by “GIS”. GIS is Geographic Information Systems and most counties use it online. It will allow you to zoom in along freeways, roads, etc. and see the individual parcels. Most sites offer options of overlaying the latest Google aerial photos so you can see if there are billboards on the parcels or if it is a possible location for a new billboard - keep in mind many aerial images are 2 years old.
Once you zoom in on a parcel, you usually can click on it and it pops up the parcel owner information for you to contact them.
Each county GIS website is different and you may have to click around to find the interactive portion of the GIS pages. But they are great tools for finding locations and the owners of the parcels. I’ve even clicked on links to find if there are easements for billboards, leases on file and available online. Some county names are the same across states so you may want to add the county name and state in your google search.