The distance Appomattox to Birmingham is 582 miles.
Say, they walked 12 hours daily at a rate of 3 miles per hour. We'd take 16 days.
However, I would believe the rail roads over this route would have been operational and
they may have been able to hitch a ride or two.