If it's a relatively complex circuit, or you really want to pack the parts into a small space, it might be helpful to grab a freeware PCB layout package. Electronic Workbench has a freeware version of their tools - in particular their PCB layout program has a mode where you can jump straight into the layout part and create wiring. It's useful because you can drag the parts around to get a feel for how the wiring will need to be connected later on. Obviously this is the no-holds-barred approach, and at some point it's easier to just do a pcboard...
For simple stuff though, pencil and paper, or just take the parts and poke them into the perfboard and eyeball out how much space/connection points you'll need.
If this is supposed to be a prototype, then treat it as such - lots of clearance and empty space. Make it organized and space _inefficient_ so that you can make changes later on. Label the important nets and test points, stuff like that.