This is what I'm doing on several projects:
For Firefox and WebKit based browsers (although beware Chrome has bugs in this area), use their CSS border-radius based styles for native rounded corners:
-webkit-border-radius: 20px;
-moz-border-radius: 20px;
These also let you specify values for each corner, just note that the syntax is slightly different:
-moz-border-radius-bottomleft: 10px;
-moz-border-radius-bottomright: 10px;
-webkit-border-bottom-left-radius: 10px;
-webkit-border-bottom-right-radius: 10px;
These are based on the CSS3 border-radius
style, more information on the different definitions here: CSS: border-radius and -moz-border-radiuss (note the article is a bit out of date but still relevant). I haven't researched this but I'm not aware of any browsers that implement the native CSS3 border-radius (please corrent me if I'm wrong).
Then for IE, I use DD_roundies which is the most elegant JavaScript solution I've seen and uses native IE VML to draw the corners.
If the user has IE without JavaScript or is using Opera, then tough luck they won't get rounded corners, but in the spirit of Progressive Enhancement this shouldn't ever be a problem.