How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and sometimes the resulting expressions are messy. What algorithms are there for converting NFA into equivalent regular expressions? Are there advantages regarding time complexity or result size? This is supposed to be a reference question. Please include a general decription of your method as well as a non-trivial example.