How do I determine if a point is inside or outside a polygon that lies on the the surface of the earth?
The inside of the polygon can be determined via the right hand rule, ie. the inside of the polygon is on your right hand side when you walk around the polygon.
The polygon may
As the globe is a sphere the normal ray crossing algorithms do not work correctly.
Use planes instead of rays. A "line" on the surface of a sphere defined by two points is an arc of a great circle (circle whose center is the center of the sphere) and is also contained in a plane that contains those two points and the center of the sphere.
Test whether the point is "greater" or "less" than the corresponding plane for each edge of the "polygon" to determine which side of the "line" it is on.
In fact the normal ray tracing and winding rule approaches work just fine on the surface of a sphere, with a little adjustment.
On the surface of a sphere a 'straight line' is a great circle and distances are measured in angular units rather than metres or inches. To draw a ray from an arbitrary point on the surface of the sphere simply form a great circle through that arbitrary point and any other point on the surface of the sphere. To keep the maths clean choose a second point about pi/2 away from the point whose location you are testing. Apply the usual even-odd rule to the great circle and your test polygon.
The winding rule also translates directly from straight lines in the plane to (segments of) great circles on a sphere.
All you need now are Java implementations of basic spherical geometry operations. I don't have any recommendations on that front, but I guess the Internet will help. For the maths start with Mathworld.
Another approach would be to project your points and polygons from the surface of the sphere to the plane -- which is what map projections do -- the topological relationship of insideness will not be affected by such a transformation.
Oh, and you'll have to decide what to do if your polygon describes a great circle
Since you're interested in a Java API for this, check out this SphericalPolygon class. It's part of a GNU GPL Java package, complete with source.