It’s certainly possible, to greater or lesser degrees between WP and Gallery, but it is a little more complicated than you describe.
What you are talking about is a “theme” (though often you will see it referred to as "a “skin” or “template”).
This is accomplished in slightly different ways by WordPRess and Gallery, but the concepts are the same. Essentially, what is invlolved is the preparation of a PHP file (or, more accurately several files) that contain the essence of your site design and “tags” that grab data from the WP or Gallery program that indicate where “stuff” from those programs is displayed.
The definitive guide to how this all works for WordPRess is found at http://codex.wordpress.org/Blog_Design_and_Layout#Themes_and_Templates
WordPress has “lots and lots” of examples of various themes others have created, and made available for you to use, on the web (check out http://themes.wordpress.net/ or large list of themes resources on the WordPress Codex
There are similar (though not as extensive) resources available for Gallery, also.