Caveat: This answer applies to private sector union workers in the U.S. The considerations that apply to public sector unions are very different. Also, as I discuss below, there are special labor relations law rules that apply to a few specific private sector industries that are pertinent to these questions.
The legal framework largely flows out of the National Labor Relations Act and the cases decided under it by the National Labor Relations Board (which is the first instance trial court in most union-management disputes), the U.S. Courts of Appeal for the various circuits, and the U.S. Supreme Court. But, I have not cited chapter and verse of particular statutory sections and cases supporting this analysis for lack of space and time (it would normally take up about a third of a one semester law school class on labor law to cover the points summarily answered below).
What are the lawful requirements of Company A in bargaining?
There is an obligation to negotiate in good faith and to make available some information necessary to allow that to be possible. The employer also can't fire an employee for insisting on negotiations in good faith with the union or for union activity.
Is there a minimal salary that must be offered (apart from minimum
wage laws)?
No.
Also, in some industries, the employer needs to pay the "prevailing wage" in order to get government contract which are critical to its business and basically amount to the union negotiated wage at comparable firms.
What happens if Company A and the union do not agree to terms?
There is no collective bargaining agreement and the employer's terms are in force when the existing collective bargaining agreement expires. Usually, if this happens, the workers then go on strike rather than working under the unilaterally employer imposed contract terms, until a new collective bargaining agreement is negotiated (and the vast majority of the time, a new collective bargaining agreement is negotiated after some period of time when the workers are on strike).
But, sometimes a prior collective bargaining agreement will establish an arbitration resolution if there is a deadlock. Arbitration is also used to resolve deadlocks, if I recall correctly, in a few key industries with large employers where avoiding a strike is critical to the nation's economy (outside the jurisdiction of the National Labor Relations Act) that are established by statute.
Can company A elect to hire people from outside the union "at-will"
while negotiating with the union?
Yes. These people are often pejoratively called "scabs" and neutrally called "replacement workers".
Generally speaking, when a strike is over, the business has to take back all of the striking workers, and fire all of the replacement workers, except to the extent that the business whose workers went on strike had vacancies when the strike started. In part, this is because this is a term of the new collective bargaining agreement and in part as a consequence of the requirement that employers not retaliate against employees for union activities. In states that are not "right to work" states, the union can prevent non-union replacement workers from being hired at all after the strike is over.
Could Company A continue to do so indefinitely, essentially no longer
employing the union members and just hiring a new group?
More or less. I can't easily summarize the case law on the point and prior collective bargaining agreement terms can be relevant.
Also, there are a few sectors of the economy (mostly the stage play industry, the movie industry, and the construction industry), in which unionization is structured on the basis of professions for an entire industry, or the entire industry in a geographical region, rather than on an employer by employer basis. This tactic doesn't work in those industries. The common thread is that work in these industries is organized on a project by project basis (i.e. a particular play, a particular movie, or a particular construction project), in which the firm paying for the project is usually a single project only entity.
Another important bright line rule is that an employer always has the right to shut down the business covered by the union entirely, rather than deal with the union.
But, this is why unions tend to be more effective in industries with large employers who can't replace the employees very easily with non-union workers (like factories and ship yards, and grocery store chains).
Is this basically saying that the only power unions ultimately have is
to quite en masse and make it difficult for the company to hire
replacements?
Basically.
But, the power to strike is considerable in most unionized employment contexts and many people won't "cross a picket line" in solidarity with striking workers.
From a consumer's perspective, not crossing a picket line means not patronizing a business whose workers are on strike. But, not crossing a picket line can also mean that workers (usually at a unionized business that is a vendor to the business whose worker's are on strike, or that deliver things to the business whose worker's are on strike) will refuse to participate in doing business with the business whose worker's are on strike.
So, even if enough replacement workers can be found to continue to operate the business, this doesn't necessarily mean that a business won't face very severe consequences for continuing to operate with replacement workers while its regular workers are on strike.
Furthermore, unions can take other actions short of strikes, like staying on the job and "working to rule" strictly refusing to show any flexibility beyond the bare requirements of their existing contract or the new one, or pursuing every single minor bump and scratch as a worker's compensation claim, reporting every Occupational Safety and Health Administration violation, or pursuing unfair labor practices litigation against the employer.
Private sector unions are declining, in part, due to the ability of employers to hire replacement workers.
Still, this is one reason for the long and steady decline of unionization in the private sector U.S. labor market (although the trend has reversed a bit in the last several years). Consider, for example, the following chart (via Wikipedia):

As I recapped the economic history of labor action in the American workforce as of December 2010:
[There have been] six general strikes in U.S. history, one in 1919 in
Seattle, and four in 1934, at the height of the Great Depression, one
in Toledo, one in Minneapolis, one in San Francisco and one at West
Coast Ports. There was also a general strike in the Commonwealth of
Puerto Rico in 1998. The last one in the English Speaking United
States was 76 years ago, and very few people living today remember it.
The United States has never had a nationwide general strike and just
two general strikes in its history, one restricted to a single
industry, and the other to a U.S. territory, extended beyond a single
city.
Union-management relations in the United States used to look a lot
like they do in Europe. Strikes were large, frequent and involved a
large share of the work force. National guard forces or private
security forces were frequently called in to put them down in bloody
conflicts. Openly socialist political parties were organized.
In 1950, a year that revisionist history remembers as a tranquil
period in American history, there were 424 strikes involving 1,000 or
more workers, in all involving 1,698,000 workers, which was more than
one in nine members of the unionized workforce of 14.3 million workers
who made up 31.5% of the total work force.
In 2008, there were 15 strikes involving 1,000 or more workers, in all
including 72,000 workers which was one in two-hundred and twenty-three
members of the unionized workforce of 16.1 million workers who made up
12.4% of the total workforce. The public sector which is 36.8% unionized, is as unionized as the private sector was at its peak. The
private sector, which is 7.2% unionized, has the lowest level of
unionization in the private sector since the 1920s, if not earlier.
The unionized workforce has remained more or less constant for half a
century, despite a growing workforce, and that masks the fact that
there has been substantial growth in public sector union membership
and a substantial decline in private sector union membership over that
time period.
The United States, there has been only one year since 1983 that more
than 3% of unionized workers went on strike (1986), and there has only
been one year since 1998 (the year 2000) when more than one in eighty
union members went on strike. In the entire United States from 1990 to
2008, there wasn't a single year that there were more than 45 strikes
involving 1,000 or more workers in the entire United States, in a
period that started with a labor force of 103 million workers and
peaked at just short of 130 million workers. In contrast, there wasn't
a single year from 1950 to 1987 that had less than 46 strikes, despite
that fact that the workforce was significantly smaller. Prior to the
1980s there were a couple hundred major strikes in the United States
per year, about ten times current levels of labor action.
I updated this account in 2014 and 2015:
There were thirteen major strikes that took place at least in part in
2015 according to the Bureau of Labor Statistics monthly tables. This
is just two more than in the year 2014, which had fewer major strikes
which involved fewer workers than any year from 1947-2013 except 2009,
a low point of the financial crisis. Most of the half century before
WWII also had more major strikes (at least proportionate to the size
of the population) than there are these days.
In all of the United States in 2014, there were just 11 strikes
involve 1,000 or more workers, which involved a total of 34,000
workers and resulted in 200,000 work-days idle, which was less than
0.01% (i.e. less than 1 day in 10,000) of the total working time of the American labor force. The year 2015 was the next most peaceful
year in post-WWII labor history.
The year 2010 also had just 11 major strikes, but those strikes
involved more workers and produced more days idle. There were just 5
major strikes in 2009 in the United States which involved fewer
workers than in 2014 and fewer days idle.
This has a lot to do with the decline of private sector unions in the
United States. . . . Just under half of union members are in the public sector
and public sector unions, as a rule in the United States, have limited
or non-existent rights to strike (although teachers unions which are a
huge part of total number of public sector union members can
frequently strike).
In 2014, just 0.001% of the working time of the American labor was
idle due to strikes or lockouts. The last year than more than 0.01% of
the working time of the American labor force was idle was 2000. The
last year that 0.10% or more of the working tie of the American labor
force was idle was 1978. Only one year from 1948 to 1959, a time often
nostalgically remembered as the "good old days" by conservatives was
below the 0.10% threshold.
Nationally, in 2014, the private sector 6.6% (7.4%) of employees were
members of unions (represented by unions), while in the public sector
35.7% (39.2%) of employees were members of unions (represented by unions), with both percentages generally tending to fall over the
previous decade.
Within the public sector, nationally, union representation rates are
highest with local government employees (45.5%), intermediate with
state government employees (32.8%), and lowest with federal employees
(31.6%).
In the United States in the year 2020 the union membership rate (the percentage of wage and salary workers who were members of unions) was 10.8 percent. . . . the union membership rate in the public sector was 34.8 percent, while the rate in the private sector was 6.3 percent.