Excel programming methodologies

Question

What are the differences in Excel programming between a UDF, Macro, Add-in, Automation Add-in, XLL, or VSTO.
Which one I should use and under which circumstances?

Answer 1

I'll try to group/oppose some of the elements you mention:

VSTO vs. VBA:
VBA (visual basic for applications) is the "classic" way to write Office automation. Excel has a development interface which you can fire from office to write macros and UDFs, and which hasn't changed for about 10 years. On the plus side, deployment is trivial, and VBA offers nice features like macro recording, which record your actions into code, and provide a good way to figure out the object model.
VSTO came about more recently, and allows you to automate office using .NET (uses COM). You can leverage all .NET and Visual Studio (ex: add WPF forms), which gives great flexibility but the deployment is more complex.
UDF vs. Macro vs. Add-In
User defined functions are custom-made methods which will stay attached to your workbook; once added gain the same status as the "built-in" Excel functions: you can call them from worksheets like =MyFunction()
Macros are procedures which will stay attached to your workbook. They can be called directly by the user, or attached to events (ex: when a worksheet is selected, do this).
Add-ins are not attached to a specific document, but to the application itself. Typically a macro or UDF is attached to the workbook: when you open the document, the code becomes available to you, and when you give the document, the code is copied as well. By contrast, Add-Ins are attached to the application: the moment you launch Excel, the add-in becomes available to you. Tools like the Solver are an Add-in. Note that Add-Ins can be written in either VBA or using VSTO (you can also write UDFs in .NET, but it's atypical).
When to use what
Add-In vs Macro/UDFs: write an add-in if your functionality should be accessible from any workbook.
VSTO or no VSTO: this is a matter of debate. Most people who are familiar with "classic" VBA automation don't like VSTO too much, because the learning curve is a bit steep. If you are used to working with .Net, this should not be a bit issue - but VSTO is somewhat quirky compared to "normal" .Net apps development.
Note also that if you use VSTO, your code can't be edited by the user. This is arguably desirable, but at the same time, Excel power-users usually know how to use VBA and macros, and expect to be able to tweak the code. That can lead to interesting discussions.
Personally, I typically use VSTO for add-ins, and I use it as soon as I see that lots of logic / procedural code is going into macros in VBA. What VSTO gives me is the ability to write testable code, in Visual Studio, and also high-performance code when heavy calculation is involved. The other reason to use VSTO is to leverage WPF to customize office.