It has been 20+ years, but the experiences I had were positive - when I lived in an area where you either had to own (or know someone who owned land) or go on overcrowded public land, a hunting lease was a must to get away. A good family friend gave me the best advice: find a way to benefit you and the land owner. Figure out if the land owner has anything he wants / needs done on the land, common interests, etc. In one case I cleaned up leftover party/camp sites and helped repair some fence...eventually ended up friends with the owner, who allowed me access year-round to just wander the property provided I didn't shoot out of season or leave a mess.
Also, a little bit of networking never helps, it's all who you know of course.