Check the "education priorities" page. Departments-->Education-->Education Priorities
If you raised salaries for government workers and still have military staffing shortages after a few months, it is likely that you have a shortage of low-level workers, medium-level managers, or both.
If the shortage is in medium level managers (i.e. officers) increase the education priority for them. Over time, more medium level managers will be trained and able to join the officer ranks. It helps if you have a decent educational system, too.
If the shortage is in low-level workers, try to find countries to do workers exchanges with, to trade surplus workers groups for low-level workers. If you play on Little Upsilon, as I am inferring by the (Little Upsilon) next to your screenname, I recommend trading workers with Country Trust B, Country Trust E, Country Trust G, Country Trust I, or Country Trust J. I find that empire has a very consistent supply of low-level workers to suit needs such as military staffing.
Workers exchanges are accessible from the Departments-->Labor-->Exchange Professionals with Others menu. Additionally, the Departments-->Labor-->Change Profession of some workers option will allow you to see if you have any LLW/MLM reserved for new facilities (such as hospitals or new corps), and give you the option of converting a limited number of professionals back into workers. The Change Profession page is a very handy indicator of whether or not you are overbuilding, but it does not include executives. (The Education Priorities page, however, does.)
I hope that helps!
