Have the USGS 7.5-quad map "Indian Cove" with you.
For the shortest approach, park at the pullout along the main park road, roughly UTM N 37-68-935, E 05-71-575 (Zone 11, NAD83). This is near a big rock outcrop and a popular pullout for drivers.
(April 2008: All topozone links are replaced by coordinates in UTM, Zone 11 NAD83, taken from the URLs of the old topozone links)
Walk across the desert flats on a south-southwest bearing toward the spot elevation of 3,812 feet shown on the USGS map, N 37-67-457, E 05-71-224. You can fudge it here: just walk south and you'll meet Quail Springs Road no matter what. You may note that Quail Springs Road heads east toward a large parking area along the main road. You could also start your hike from here but it's a lot longer of a walk, over a mile extra each way.
Enter into Johnny Lang Canyon on the road heading south. It's a good road for a bit, then disappears into the brush and braids in and out of the sandy wash bottom. At some point you'll have to ascend out of the canyon. Use your instincts here. We ascended at roughly N 37-64-567, E 05-71-915.
Next, walk up the steep hillsides, working your way up and over toward a ridgeline/saddle that's roughly south of peak 5,405. You should be roughly N 37-63-759, E 05-71-346.
Quail Mountain is now in view. Descend across easy slopes to a low point east of the peak about N 37-63-271, E 05-70-919.
Hike up an open ridge to the summit. The way will be obvious. The summit is elongated. Be sure to explore the northern rocks and the southern wind shelters. The highest point seems to be on the south end of the peak. The views are tremendous, especially to the south where there's almost a vertical mile of elevation differential. The Salton Sea might be visible to the southeast. Huge Mt San Jacinto is to the southwest.
We descended a steep gully that trended northeast off the summit (N 37-63-809, E 05-70-279). This had been suggested as a way up by some locals in Joshua Tree, but it is extremely brushy and steep, with a number of short class-3 scrambles. While it's not overly technical, it demands exacting nav for the ascent. Our descent went well, but it took us quite awhile to manage the whole route. We did come upon a complete skeleton of a mountain goat ram on the ground!
Long pants are a must. Hiking poles are advised, partly to beat the brush for critters. This is serious rattlesnake country! Bring pliers or a comb for the cactus, and carry in all water. It's a good 10+ miles round trip with about 2,300 feet of gain.
Other RoutesThe Sierra Club 100 Peaks Section
website has information for other possible routes to the top. Thanks to Bob Burd for suggesting the link!