What are the regulations and testing that determine whether a "Spins Prohibited" placard is required in an aircraft?
Spins require a demonstration for certification, but can be bypassed with an FAA waiver as Cirrus did for the SR-20/22. The waiver was granted under the understanding that the only way to recover a Cirrus is to pull the chute.
FAA CFR Part 23 governs the process and requirements for certifying general aviation aircraft. Specifically for spins you are wanting to read CFR 23.221 which outlines the process of spin testing:

(a) Normal category airplanes. A single-engine, normal category airplane must be able to recover from a one-turn spin or a three-second spin, whichever takes longer, in not more than one additional turn after initiation of the first control action for recovery, or demonstrate compliance with the optional spin resistant requirements of this section.
(1) The following apply to one turn or three second spins:
(i) For both the flaps-retracted and flaps-extended conditions, the applicable airspeed limit and positive limit maneuvering load factor must not be exceeded;
(ii) No control forces or characteristic encountered during the spin or recovery may adversely affect prompt recovery;
(iii) It must be impossible to obtain unrecoverable spins with any use of the flight or engine power controls either at the entry into or during the spin; and
(iv) For the flaps-extended condition, the flaps may be retracted during the recovery but not before rotation has ceased.
(2) At the applicant's option, the airplane may be demonstrated to be spin resistant by the following:
(i) During the stall maneuver contained in §23.201, the pitch control must be pulled back and held against the stop. Then, using ailerons and rudders in the proper direction, it must be possible to maintain wings-level flight within 15 degrees of bank and to roll the airplane from a 30 degree bank in one direction to a 30 degree bank in the other direction;
(ii) Reduce the airplane speed using pitch control at a rate of approximately one knot per second until the pitch control reaches the stop; then, with the pitch control pulled back and held against the stop, apply full rudder control in a manner to promote spin entry for a period of seven seconds or through a 360 degree heading change, whichever occurs first. If the 360 degree heading change is reached first, it must have taken no fewer than four seconds. This maneuver must be performed first with the ailerons in the neutral position, and then with the ailerons deflected opposite the direction of turn in the most adverse manner. Power and airplane configuration must be set in accordance with §23.201(e) without change during the maneuver. At the end of seven seconds or a 360 degree heading change, the airplane must respond immediately and normally to primary flight controls applied to regain coordinated, unstalled flight without reversal of control effect and without exceeding the temporary control forces specified by §23.143(c); and
(iii) Compliance with §§23.201 and 23.203 must be demonstrated with the airplane in uncoordinated flight, corresponding to one ball width displacement on a slip-skid indicator, unless one ball width displacement cannot be obtained with full rudder, in which case the demonstration must be with full rudder applied.
(b) Utility category airplanes. A utility category airplane must meet the requirements of paragraph (a) of this section. In addition, the requirements of paragraph (c) of this section and §23.807(b)(7) must be met if approval for spinning is requested.
(c) Acrobatic category airplanes. An acrobatic category airplane must meet the spin requirements of paragraph (a) of this section and §23.807(b)(6). In addition, the following requirements must be met in each configuration for which approval for spinning is requested:
(1) The airplane must recover from any point in a spin up to and including six turns, or any greater number of turns for which certification is requested, in not more than one and one-half additional turns after initiation of the first control action for recovery. However, beyond three turns, the spin may be discontinued if spiral characteristics appear.
(2) The applicable airspeed limits and limit maneuvering load factors must not be exceeded. For flaps-extended configurations for which approval is requested, the flaps must not be retracted during the recovery.
(3) It must be impossible to obtain unrecoverable spins with any use of the flight or engine power controls either at the entry into or during the spin.
(4) There must be no characteristics during the spin (such as excessive rates of rotation or extreme oscillatory motion) that might prevent a successful recovery due to disorientation or incapacitation of the pilot.

Another good read is the Aircraft Certification Service - FAA Flight Test Responsibilities, Procedures, and Training which states:

506. Spin Tests. Spin tests conducted by FAA FTPs should be flown initially with a spin chute (or equivalent equipment) installed on the aircraft and approved by an FAA structural and/or systems engineer. (See Appendix 3 for additional guidance on requirements for spin recovery devices). After all spin modes have been evaluated and found satisfactory, the spin characteristics should be checked with the external spin chute removed, unless it is determined
that the spin chute installation has no significant effect on spin characteristics.

(Emphasis Mine)