(Some of this answer was previously posted as an answer to the question How to find wife's maiden name in New England in the 1700s?, but I have added material which is specific to Iowa.)
The Family Search Wiki has several reference articles on researching women ancestors.
Information in this Wiki page is excerpted from the online course
Research: Grandmothers, Mothers and Daughters-Tracing Women
offered by The National Institute for Genealogical Studies. To learn
more about this course or other courses available from the
Institute, see our website. We can be contacted at
Of the references listed there, I am most familiar with this book:
Schaefer, Christina Kassabian, The Hidden Half of the Family: A Sourcebook for
Women’s Genealogy (Baltimore, Maryland: Genealogical
Publishing Co., 1999).
For each of the 50 states, the author provides a timeline for important dates in state history, changes in the laws governing marriage and divorce, property and inheritance. She suggests where to look for records, offers a bibliography, and lists resources for studying women's history. The introductory material, including "how to use this book", discusses the problem of searching for records pertaining to women. Iowa is listed on page 116-119. One online resource listed there is the Iowa Women's Archives at the University of Iowa Library.
Most of the time, I learn maiden names of women by finding records which list people in family groups -- anything which is likely to name a person along with the names of their daughters, their parents, or their sisters (both married and single). Probate records and other court documents can be especially useful, as well as newspapers. Schaefer's book is
a useful finding aid for many of these records.
For instance, her section "where to find Marriage and Divorce Records" gives us the timeline of record availability. County clerks began recording marriages in 1834. Statewide registration begins in 1880. So it is not surprising to see that the record you've been able to retrieve from FamilySearch was recorded at the county level. Keep in mind that a prior marriage may not have been in the same county. If his marriage to Martha is a second marriage, might George's first marriage have been in a neighboring county?
Also, don't forget that counties, like people, are 'born'. Have you checked when the counties in this area came into being? It's possible that a person like George could be married twice in the same place, but if a new county was created in the interval, the first marriage could be recorded in one county, and the second marriage could be recorded in another. Have you looked for church records?
Schaffer says several territorial and state censuses are available at the Iowa State Historical Society, which has since been renamed the State Historical Society of Iowa; the 1838 territorial census is available on microfiche at the University of Northern Iowa Library.
Whenever I get stuck, I like to read case histories from other people looking in the same place and time period to get clues from their descriptions of how they solved their problems. Books and articles like this, and others where genealogists detail their own research, can be a good place to get ideas of how and where to search. Can you find bloggers whose work is in the same area in Iowa?
Studying friends, associates, neighbors can also be a good way to build a picture of the entire community and can sometimes yield records that you missed because of poor indexing. See Elizabeth Shown Mills' Quicklesson 11: Identity and the FAN principle.