I'm a genealogist of almost 40 years. Although you're touching on a couple of areas that I really haven't had to dig in to, we do have extensive holdings located at these two links.
Don't be too concerned about getting into specifics with any questions you may have. Someone on here is bound to know the answer.
This isn't limited to Native American and African American research, but in my experience as a genealogist and archivist, there are three key questions a genealogist needs to ask when considering federal records. How might my person/family have interacted with the federal government, and where, and when.
The "how" helps you determine the agency or agencies that might have created records; the "where" and the "when" help you track down the current location of those records. Most archival records of agencies are distributed according to the location of the creating office and the time period.
It's not always possible to answer the "how" in advance. The "where" and "when" of the subject's life are always valuable pieces of information in tracking down archival records.
Since you teach library users about different research tools, the archives.gov website has specific sections for teachers resources and investigating genealogical resources also. Special topics and tools with teachers resources can help in this regard. http://www.archives.gov/education/special-topics.html
Additional historical information on Native Americans can be found in the DocsTeach section of the Teachers Resources tab. This feature focuses on teaching different historical topics through documents held by the National Archives. This is a very helpful tool that I've used before and there are lots of classroom plans and teaching aids for lecturing on genealogy. http://docsteach.org/
There's a great African-American section in the Civil War Soldiers and Sailors database (http://www.nps.gov/civilwar/soldiers-and-sailors-database.htm). Although it's hosted on the National Park Service site, it was a joint project with NARA originally.