Yes, DVDLab can create a simple menu, or most other authoring programs can as well.
Once you have a menu, the PS2 will read the menu first, then it can play the movie.
It's got to do with "firstplay" and VTS/Root settings in the DVD structure.
In the manual for your PS2 it explains a bit about it.
Also, if you have an older PS2 I believe a ver 4 or earlier you have to use -R disks, but the newer ones seem to like the +R better, but should be capable of playing both formats. You really need to look at buying some good DVD media like Taiyo Yuden if you plan on watching movies on your PS2