Everyone else from the USAF chime in on this one please.
From what I understand, it depends on the regional affiliation. With Chiba Sensei and the Western Region, there are actual tests for Fukushidoin and Shidoin, and I think he's looking for a level of clarity and proficency in his teachers. F starts at Nidan, and S at Yondan.
With Shibata Sensei, it is based on his recommendation, as he knows all the students within his organization.
With the ER, it is also (I think) based on recommendation. Have no idea how it works in the Midwest region.
Why not ask the teacher whose dojo you wish to join?