Last updated Feb 26, 2016:Firefox 35 finally implemented -moz-appearance:none to make the native select invisible. For older FF versions, we can use -moz-calc() which works back to FF4 to over-size the select by 1.5em to make things looks great back to FF4. Qualify styles inside a support block.
How this works: This styles a native select consistently cross-platform with only minimal CSS. The native select is then styled so it is essentially invisible (no appearance, border, bg) leaving only the select's text visible. There is a wrapper around the select that has the majority of the button styles (gradient, shadow, border, etc.). We then add the custom arrow via a pseudo element to the right.
Confirmed to work in the following browsers
This technique seems to be functional everywhere since we're still leaving the native select in place. Worst case, the native select styling and the custom arrow will both show up but in all popular platforms, this looks very good and consistent. One minor caveat: setting the select to 110% means the menu may open up a bit wider than expected in Firefox. Visual Test results
Custom select styled consistently
iOS 4/5/6/7/8 - looks good, iOS3 even works fine but isn't quite as pretty
Android 2.2/2.3 (Browser) - looks good
Android 4.0/4.1/4.2 (Browser) - looks good
Android 4.0/4.1/4.2/4.3/4.4 (Chrome) - looks good
WP8 - looks good
Kindle Fire 2/HD - looks good
IE 10/11 - looks good
Safari 5 - looks good
Chrome 22-35 - looks good
Opera 15-22 - looks good
Custom select with minor visual issues
iOS3 even works fine but isn't quite as pretty
Firefox (version 4-34) - select menu when open is wider then it needs to be (by ~20px) to clip off the native arrow. Note that the select text can run under the arrow, no solution found for that.
Opera Mini - alignment of text and arrows is a bit off but it works
Opera Mobile - custom and native arrows both appear
Nokia Asha - Long options can break outside the box