Adding New Header

that depends:

if the header image is in an img tag
– then you could look into using conditional tags such as is_page() http://codex.wordpress.org/Conditional_Tags

if it is a background image in the css
– then you could work with the body_class() (if your theme uses it);
– or conditional background styles in header.php

best approach would be if you could name the theme you are working with (if it is a free theme)
and post a link to your site.

twenty ten has build-in that if you set a featured image (in a page) of at least the dimensions of the header image, this image should then be shown as header image.
you find the size in functions.php, for instance:

define( 'HEADER_IMAGE_WIDTH', apply_filters( 'twentyten_header_image_width', 940 ) );
	define( 'HEADER_IMAGE_HEIGHT', apply_filters( 'twentyten_header_image_height', 198 ) );

I replaced the default header with my own jpg.

did you do this in ‘appearance’ ‘header’ ?
then this should not interfere.

When I go to create a new page I am not seeing a way to put a different header on just that page.

try to set an featured image (on the right, a bit lower)
the image needs to have at least the dimensions of the header image (940 * 198 px in standard twenty ten)