According to wikipedia:
The first president to issue a signing statement was James Monroe.
Since Monroe, and again according to wikipedia, until the 1980s those statements where not much more than "triumphal, rhetorical, or political proclamations".
Apparently they became more popular with a memo from the staff attorney in the Justice Department's Office of Legal Counsel Samuel A. Alito (now Associate Justice of the Supreme Court of the United States), that made the case for
"interpretive signing statements" as a tool to "increase the power of the Executive to shape the law." Alito proposed adding signing statements to a "reasonable number of bills" as a pilot project, but warned that "Congress is likely to resent the fact that the President will get in the last word on questions of interpretation."
So to resume the answer to the first part of your question, it seems that until 1986 memo they were not considered to carry any extralegal power. Only after the publication of that memo did the number issued grow exponentially.
For the second part I will again refer to the same wikipedia article:
[T]he Court may have addressed the matter in Clinton v. City of New York (1998), which invalidated the line-item veto because it violated bicameralism and presentment.
as well as
In Hamdan v. Rumsfeld (2006), the Supreme Court gave no weight to a signing statement in interpreting the Detainee Treatment Act of 2005, according to that case's dissent (which included Justice Alito).
So it seems that while it is not considered Constitutionally invalid it does not necessarily need to be considered by Justices when ruling. Thus the extralegal power of a signing statement nowadays is only considered important "if Congress has not directly spoken to the precise question at issue"