Du får leite etter steder de har bodd, - her er vel han og faren i 1900 folketellinga? http://digitalarkivet.arkivverket.no/ft/person/pf01037527001219
Du her an merkelighet med mellomnavnet til faren, Annanias Martin, også.
Det ser ut som at han kun ble døpt Annanias, men i dåpen til Peder står det Ananias Martin Gundersen.
http://www.arkivverket.no/URN:kb_read?idx_kildeid=16652&idx_id=...
http://www.arkivverket.no/URN:kb_read?idx_kildeid=15740&idx_id=...
Det er forresten feil fødselsdato på moren hans, Karen Bergitte Edisdatter.
Både i hennes dåp og giftermål står det 8 April 1836, samt navnet på foreldrene hennes hvis du vil bygge videre der.
Du får leite opp originalene for flere detaljer:
https://familysearch.org/pal:/MM9.1.1/N4TF-CSQ
https://familysearch.org/pal:/MM9.1.1/NWHR-7MR
Google Maps sier det er en Valle i Steigen og en Valle i Gildeskål. Det er også verd å sjekke "Norske Gårdsnavn".
Digitalarkivet vet også om en del Valle-gårder i Nordland:
http://digitalarkivet.arkivverket.no/sok/eiendom?s=valle+nordland
Jeg vil tro at Valle i Steigen (som Harald sier over) er "best guess".
Dette siden Peder Andreas er født i Nordfolden-Kjerringøy herred (Vågen) og Valle i Steigen ligger under dette herrede.
Gildeskål var eget herred (1838) under ft i 1900, så da hadde han vel i så fall vært døpt i Gildeskål herred om det var den "Vallen" han har tilknytning til.
Men for all del, jeg kan jo ta feil. Og mer konkret hvorfor han tok (hvis det i det hele tatt var han som tok) navnet "Valle" ("Walle"), kan være flere årsaker.
Har for øvrig samme dillemma selv siden min forfadder Ove Theodor var født Engebretsen, men plutselig endret navn til Lynnæs, uten noen opplagt og kjent grunn.