How to implement High Availability for all nodes in a sharded database?
There's no difference in HA solutions when you break up a large database into multiple smaller ones.  Either Availability Groups or Failover Cluster Instances will work.
AGs have the benefit that you can perform cross-shard queries on any instance that has readable replicas of all of the shards.  So, for instance you can have a shared database that's always present on every node, and the app can always perform cross-database queries from.  Just note that cross-database transactions (including all writes) are not supported except between databases in the same AG (not blocked though).