When is it necessary to redirect a user to another page after submitting a form versus just being on the same page but with a "success" message on top?
Is this appropriate for small forms like "Contact Us" (which is located on a small sidebar)?
Any page where they need to be redirected either way should have it. For example, a login page usually redirects to the index with a success message on the top, that makes sense. Whereas a comment page usually just loads a success message on the top since it just refreshes that same page to show your comment.
It all depends on what type of form it is, where it is, and what happens when you click submit.
It's never really necessary, but it is nice to get a success message loaded onto the page automatically, instead of redirecting you, unless the redirect is necessary for other purposes.
Depending on the action that preceded it, a simple message confirming the submission process was received and processed may not be sufficient.
For example, in a post that is part of a business transaction a detailed confirmation page may be necessary either to provide the user with important new information (such as a confirmation number) or a detailed summary of the transaction that was just completed (such as a line item receipt).
In these cases it may be a better experience for the user to see that information in a new "page" whether that is a full page refresh or just an asynchronous refresh of a large portion of the page.
As always it depends on the particular use case and what best serves the user, but the general guidelines above are a good place to start.
In many cases, including the one you described, success pages seem to be yet another archaic pattern we inherited from times when programming was significantly "harder".
Most of these have been replaced by ajax-style on-page success & error-messages.
However, there are cases where a custom "success" page could be useful.
For example, upon completing a purchase in an e-commerce store, you could send a customer to a custom page, where you thank them for their purchase, allow them to share the purchase with their friends, but also suggest some related products.
It really depends on what the "next logical action" would be.
I look at the necessity of the success page as a function of the contents of the page submitting it. A page that is mainly form content, when submitted, should show some kind of success page. Pages where the form is secondary, like a small "contact us" area or a comment field, are better if they show a conformation message in place of the form. A confirmation page is OK, but not ideal.
This applies to submission type tasks. When it comes to action type tasks, it's different - a small login form should usually go to some kind of account screen, or at the least, reloading the entire current page so the "logged-in view" of the site can be shown.
In cases of transactions it is essential to provide some feedback indicating whether it is complete or not. One clear example I could state is an ecommerce website. After completing a payment, not redirecting to a success page will leave the user anxious and confused.
A non-monetary transaction that may require a success/ failure acknowledgment could be a job site. After submission of details one would most certainly want an acknowledgment in the form of a success page.
Small forms like "contact" us may do a quick AJAX post and avoid redirection.