The north star is easy, just fine the big dipper, and the two outer stars that form the cup form a line towards the north star. Not sure on the southern cross since I've never lived down there. I suppose when you're really close to the equator that you'll just have to aim north or south to get the rotation point though! http://coolcosmos.ipac.caltech.edu/c.../northstar.gif

If you don't want star trails, you will be limited to about 20 or 30 seconds before the stars start becoming elongated. In that case, use ISO 800 or higher, and open the aperture up. Wide open on the 15-85 should be fine. Give that a go and see how it works for you. It really depends on what time of night it is, and where the moon is, so you'll have to play with it. Make sure to shoot in RAW so that you can increase the exposure if needed! And when you are reviewing images on your camera outside, they will always look brighter than when you go back inside and put it on your computer, so if it looks just right, you should probably expose by one more stop or so! You could play around with light painting the foreground of your composition with a flashlight as well.