Rounded corners does present a challenge, but it's not too bad. This site has a great listing of the many methods that you can use for rounded corners.
http://www.cssjuice.com/25-rounded-c...ques-with-css/

As for gradients, the easiest way is to make an tall thin image of the gradient, say 5px by "height of your header", then repeat that image horizontally as the background.