17th cent. Old Spanish vuasted, vuested, vusted. From vuestra merced (15th cent.). For a counter argument, however, see Menocal (1984), who argues an origin in Arabic ustad "professor."
In Latin America, usted is both formal and informal senses in the plural. In Spain, broadly speaking, usted is strictly formal.