When you're dealing with unfamiliar geography, especially historical geography, maps can be quite useful.
I found this map of 1320 Brandenburg. (source) It is believed the territory called Neumark is the origin of our surname. You can note that the Oder and Warthe rivers form one of the boundaries.
I am only able to trace my particular Newmark ancestors back to Warka, Poland, near Warsaw. How did they travel there? They could have traveled most of the way by following Poland's river system, with minimal land crossing near Bydgoszcz. (The Oder and Warta rivers can be found in the upper left.) We have no idea when they left Neumark, and entered Poland. All we know is that they were in Warka by the 1880s.