The National Labor Relations Act (NLRA) is the primary legislation which gives private sector unions in the U.S., that are in a unionized bargaining unit that is recognized by the National Labor Relations Board, authority to negotiate contracts and to include mandatory grievance procedures on behalf of all employees in the bargaining unit (typically some form of binding arbitration), even if the union would not have had the authority to do so otherwise under the common law of contract and agency.
Public sector unionization is a more legally complicated concept because it is regulated on a state by state basis, in addition to laws regulating federal government public sector unions that is separate from the NLRA structure, and because civil service laws that apply to almost all public employees except a small number of political appointees, address many issues that would be addressed in a private sector as part of a collective bargaining agreement and apply whether or not a particular employee is part of a public sector union, so I'll limit my answer to private sector unions in the U.S.
For what it worth, the legal theory and actual practice of union-management relations and labor law in the United States is quite atypical of most other countries, and other countries are also very non-uniform in their laws regarding union-management relations.
In France, for example (where the union movement is especially strong), while it is illegal, abducting senior managers and physically threatening them in order to secure a favorable collective bargaining agreement is a practice that is widely tolerated by both companies and the government.
Would that mean that unions have powers of attorneys over labor
This isn't the functional mechanism by which this is done (instead, it is a provision in a Collective Bargaining Agreement reached between the union and the employer). Like agents pursuant to a power of attorney, unions have fiduciary obligations to their members that impact how disputes are handled on behalf of their members and can be legally enforced by unionized employees if breached by the union. So, conceptually, the idea of the union having a POA from their members isn't far from the mark.
If it's not mandated by law, what if a union contract does specify
that unions do have the power to represent all employees in all labor
Such a clause is valid and enforceable. It is also worth noting that such clauses are frequently not comprehensive, and often leave open some kinds issues that the employee may pursue separately. There isn't a uniform national rule, it is negotiated on a case by case basis. Typically, it is the employer that will push to require all cases to arbitrated by the union to keep it out of the courts and secure a more rapid resolution of recurring points of dispute.
Would that alone make it incumbent on the union to inform (for
example, new employees) of their rights to seek representation in
cases of (for example) salary disputes?
Employees in a unionized workplace are informed and must be informed, at the outset that they are represented by a union and are typically given access to information about the nature of that union representation by the union upon being hired or within a day or two afterwards.