Russia is a tough one - mostly because it's so large and the borders in Eastern Europe kept changing in the late 1800s/early 1900s. Here's a helpful link from Archives.org about Russian genealogy and borders, and a pretty interesting article from About regarding contacting Russian archives. It really helps if you have even a general area of Russia pinned down. Have you found any immigration records for her yet? Depending on when she came to North America, the record may list the name of a relative back in Russia. If you think she and Charles married in New York, you could try tracking down a marriage record which may give her birthplace and parents' names.
Here are some Russian records available free on FamilySearch.