We have moved onto our new place.  we are doing our own hay which has already been baled. 

When do I test my soil and hay? I'm in Oklahoma

and who do you use to test?

http://soiltesting.okstate.edu/

You can find info on taking your soil and and forage tests at the above link.  There's links for how to take your samples, where to send, etc.  Your local extension agent can certainly help also.  That's what they are there for.  :)

As to when to test.  I personally would test my hay crop each year and calculate any additional mineral needs for my horses.

Your soil test depends on your production goals... if you are just wanting to grow a little bit of hay for your own use or multiple cuttings to feed several horses, etc.  Since you have just moved there, I would soil test now to get a handle on any lime, potassium and phosphorus needs which you could put out soon to ensure availability next spring.  Wait until spring to apply any nitrogen needs.  When you submit your samples to the lab above, you should get a recommendation on what fertilizer would be needed.  I forget how exactly OSU does their recs but some states recommend just what is needed and some a little extra.  You would be somewhat ok depending on what your goals are applying the same amount of p and k for a couple of years before you have to soil test again.  Put out the needed nitrogen each spring.

It doesn't hurt to test every year however the only thing that is probably beneficial is protein content. Total digestive nutrient or TDN only has to do with cows and several other things they test for affects cows. We had our hay tested every year for all those things but my dad sold hay and most of it was sold to people who had cattle. I do know that the main thing my dad was interested was the protein content. Our agricultural agent had a core sample thing that you screwed down into the bale of hay. You can test your own soil or send it off through your agricultural agent. 

If you make 3 crops of hay a year.   You really need to test each crop.  The test is only as good as your representative sample that you take.

On your soil test.  Take one now.  When you send it in make sure to tell the lab that you are growing hay and what kind of hay. It will make a difference in the recommendation. It takes years to change soils and availabilty of nutrients.  Hay removes far more nutrients from the soil per year than does raising grains.