How to change/add to schema in a SQL Server Always On Availability Group?
I am wondering how should I go about adding a new table, or modifying the schema of an existing table in an Always On Availability group without incurring downtime?

If you Always On availability group is set up correctly and sync is working no downtime is required. Connect to the primary (preferably using listener) and do your change in the same way you will be doing in a stand-alone server. 

Is this fully automatic? 

Yes, it is fully automated.

I simply go ahead and create my table on the primary in an availability database and it will then get replicated to the secondary?

Yes, it will get replicated to all secondary nodes (assuming your sync is working correctly).

Few more resources to read on this:


Do schema changes “break” Availability Groups or are they handled transparently?
Whitepaper: Microsoft SQL Server AlwaysOn Solutions Guide for High Availability and Disaster Recovery