Ouch! EWR-LAS is a tough route to get cheep! Very little competition. Here are some general tips:

Check Continental, America West, Delta and Northwest. Often a flight on CO can be purchased for less as an HP codeshare.

Typical V fare is $300-500 US. Red-eye travel is cheaper. If you go CO, purchase the Las Vegas book by Entertainment publications. Good CO discount you can use (not restricted at EWR).

Travel Agents get cheaper fares for booking packages with less popular hotels (Riverria, etc). If you also need hotel, try this....

Then there's always priceline.com.

Good luck