1. I am trying to find where my great grand father William Mann was during the reconstruction period
a) In 1870 he was in Port Gibson, MS. This was just a few years after the Civil War. He had a daughter, Mary B. that was born in MS in 1860. So, it would appear that he was in or near MS in 1860 and there again by 1870. What about the years between the two dates?
Per the 1870 census, he was born around 1837.
Maybe he served in the Civil War. If so, then he could have come home to the MS Black Codes and decided to leave. Why VA? Could his wife have had relatives still in Virginia? Did he move there for work? Did he move with other family and friends?
b) Mississippi Reconstruction
In 1865, MS enacted the first of the restrictive Black Codes.
It was to get even worse ...
Any adult freedmen found without employment would be fined and put in prison. The newly freed was subject to a tax that if not paid, would result in a fine / prison term. He could then be hired out without his consent until the tax and an additional fine were paid. His children were subject to involuntary apprenticeship.
Freedmen could not live (rent or purchase) outside of town, they could not work for longer than 30 days without a contract, could not leave their employment or break their contract, could not gather in groups, and could not hold religous services with a un-licensed minister.
Other more restrictive laws followed, making Post Civil War Mississippi life worse than slavery for many freedmen.
The formal end of the Reconstruction period was in 1877.
c) Freedmen's Bureau
For more historical information, check the description of the records of the Bureau of Refugees, Freedmen and Abandoned Lands.
2. If William was born in Port Gipson, how did Mary arrive there...
There were no slaveholders that I could locate name Mann in the Port Gipson area.
a) There were MANN slaveholders in Choctaw, Itawamba, Lawrence, Leake, Madison, Marshall, Monroe, Neshoba, Tishomingo and Warren counties. Warren is just north of Claiborne county.
Search marriage records for Mary's maiden name. Was she actually enslaved? in Mississippi? Was her slaveholder in Mississippi?
If so, then he MAY be found with the same surname (not always).
Mary (Lizzie) was born abt 1837 in VA and living in MS in 1869-1870 (at 33 years old). If Mary B. is her natural child, then she Lizzie was in MS by 1860 and in Claiborne parish in 1870.
How did she get to MS?
Perhaps Mary E. was 'sold down south' with family members before the Civil War.
It is also possible that she was in a neighboring county or STATE, and met William either in or near Port Gibson, MS. Families moved in search of work and/or a safer and more secure environment.
There are MANY MANY possibilities, none of which can be confirmed without more information on Mary Eliza/Lizzie.
Obtaining her maiden name is a start.