Mega, This is a question that I think a lot of people have...where is it ok to hike into the woods, forest, mountains, etc and setup camp where you desire. Then spend the night by a fire and continue on the next morning. I'm assuming its not about how to get the perfect picture of a tent.
I can't help with respect to Oklahoma, but I can give some ideas as they relate to the US southeast. In my region of the country there are two primary options. The first is National Forest Land. The forests managed by the Forest Service are for multiple use purpose. This includes hiking, camping, and backpacking. Typically you do not need a permit or pay a fee (not true of all areas though). You simply find a trail head and head out. You can camp where you like...usually not too close to streams and trails. The NF's near me often have less developed trails or trails that may use roads for connections. Be warned that National Forest multiple use may also include hunting, logging, or off road vehicles. A national forest in NC that work as described is the Pisgah National Forest. In the Pisgah you can camp where you like, build fires, all without a permit or fee.
Here is a pic in the Pisgah, NF. A big stream is nearby.
The second option is the National Parks. Unlike the National Forests, the use off each park is much more regulated and the availability of backpacking depends on each park. Also if a park allows backpacking you will typically pay a fee and be required to register. The regulations for camping, fires, etc are usually more strigent then in the national forest. Unlike the NF's the park's mission is preservation, not multiple use so you will not find hunting or logging in a park. An example of a park that support backpacking is the Shenandoah in VA. Here you can camp anywhere as long as not too close to streams and trails. You have to register and pay a fee ($15 I think). You can not build fires though.
Here is a pic in Shenandoah, I camped just on the other side of the creek.
Here is a link to my website which has links to both the Park Service and Forest Service. This is a good place to start researching areas.
Once you have found an area that will allow the type of backcountry experience you are after you will need a map. I have had great luck with National Geographic Trails Maps. If one is not available I'd find a NSGS Topo Quad for the area of interest.
The next thing is learning to read a topo map so you can identify areas that will support a camp. With some practice you will be able to spot likely areas that flat enough to camp, have a nice view of a valley or stream, and has water nearby.
Sometimes a spot is exactly as I imagined it and sometimes I couldn't be more wrong. But its always a learning experience that makes me better.
Here is one of my favorite spots near Mount Rogers, VA.
So these pics may not be the perfect spot, but they were all spots I had picked out first by finding a park or forest I could backpack in. Then I planned a route and picked a spot on a map that I thought would be good places to camp.