Saving data: Program Files vs AppData [Windows]

The location of the folder itself actually answers the question. But for clarity, let me explain anyway.

The AppData folder is located in a user's folder, eg: C:\Users\Username\AppData, whereas the program files folder is located in C:\

The biggest difference here is permissions. If you have just one user on your pc, then that user has all rights everywhere and it may not make sense. But if you have multiple users, then it starts to make sense. Each individual user has its own folder in C:\Users, with their own AppData folder. Not only does this mean that other users do not have access to your AppData folder, but it also allows one program to be installed just once, yet have settings for every user.

For example, if you have Mozilla Thunderbird or Microsoft Outlook (they are email clients for those who are not aware of either), you would not want to install the application again and again for every user. You would rather want to install the application just once, but have different settings per users. Because not every user will have the same email address.

For that reason, AppData exists. For a users's settings.

A second reason is security. Although Program Files could be the place for programs that just perform a task and have no settings, if a user is not an administrator on that pc, they cannot write to the Program Files folder, so the program itself cannot make changes at all. In AppData however, the user always have rights to write there, even if they are not administrators. So a program that needs to write data, for example a webbrowser with its cache will have to use AppData to write that cache or the user would get an UAC prompt asking for administrative access everytime they start the program.

why do programs save their data in the AppData folder and not in their Program Files' installation folder?

Program Files is for storing the program itself, AppData is to store user specific information related to the program. (And ProgramData is to store not user-specific information related to the program).

Do they actually store all their local data in the AppData folder, or can they store it wherever they like?

As mentioned already above they can also store it in ProgramData, and both are just general behaviour, there are also programs just creating their own folder in C:\, or in Documents folder.

Here is a broader summary of how programs store data: https://www.howtogeek.com/278562/what-is-the-programdata-folder-in-windows/