Does WordPress send a 301 header message when you change permalink structures?

Yes, WordPress will do a “301: Moved Permanently” to the “real” URL. WordPress calls this “canonical”. When it hits a 404, WordPress will do a lookup on the URL fragments and attempt to find a post / page with that slug. If it finds one – it will do a wp_redirect() to the proper permalink of the post.