You have more freedom when hand wiring on a proto board, because you can cross wires anywhere and as often as you want. Without knowing more about your project, the signals, the packaging, etc, here are some general thoughts.
Start with a schematic that is as clear and uncluttered as possible. Move the parts around to minimize the number of crossed signals. This can lead to a approximate parts placement map on the board that has short, direct signal runs. If the schematic shows an organized flow of signal paths from inputs to outputs, that will drive a similar flow on the board.
Things like octal registers have numbers assigned to I/O pins, but these are not rigidly defined bit values. Sometimes the out0 to out7 arrangement is the exact opposite of the in0 to in7 arrangement of whatever the outputs are driving, and flipping over the outputs now becomes a nice flat parallel run. Of course if you move the output bit positions around you have to move the corresponding inputs, and this might create more problems that it solves. You won't know until you are further into the design and layout, but it is something to keep in mind.
Similarly, when assigning individual gates in logic devices, think about their placement in the package. Often this doesn't become clear until you are in the wiring phase - you'll see that if you swap these two gates here, or swap a gate in this chip for an identical one in another chip, it reduces signal crossing and clutter. Then go back and edit the schematic to reflect the final wiring.
Since the power and ground connections to the chips presumably will not change during debugging, put all of them down first and run the signal wires over them. Don't forget the decoupling capacitors at each power pin.