Knighthood and Andal Culture
You don't need to specifically narrow down your question to Andals. Knighthood is an Andal institution. The Would-be Knights generally have to swear vows in name of the seven gods of Andals and they have to stand a vigil in a sept. Which is why Knights are very rare (But not unheard of) in Iron Islands & North. As evident from Knighting ceremony procedure:
a touch on the right shoulder with the blade. "In the name of the
Warrior I charge you to be brave."
The sword moves from right shoulder to left. "In the name of the
Father I charge you to be just."
Right shoulder. "In the name of the Mother I charge you to defend
the young and innocent."
The left. "In the name of the Maid I charge you to protect all
women....
Ironborn and Northmen do not consider these deities true therefore they do not usually get involved with Knighthood.
However, I just observed that a generic oath can also be used without specifically mentioning the deities.
A wan smile crossed Lord Beric’s lips. “Thoros, my sword.”
This
time the lightning lord did not set the blade afire, but merely laid
it light on Gendry’s shoulder. “Gendry, do you swear before the eyes
of gods and men to defend those who cannot defend themselves, to
protect all women and children, to obey your captains, your liege
lord, and your king, to fight bravely when needed and do such other
tasks as are laid upon you, however hard or humble or dangerous they
may be?”
“I do, m’lord.”
The marcher lord moved the sword from
the right shoulder to the left, and said, “Arise Ser Gendry, knight
of the hollow hill, and be welcome to our brotherhood.”
A Storm of Swords - Arya VIII
What makes a Knight?
Any Knight can make a Knight. All you need is someone who is a Knight, he can then hear your vows and dub you a Knight. Ser Lyonel Baratheon said this to Ser Duncan the Tall in The Hedge Knight:
"The lad has the truth of it," said Ser Lyonel Baratheon. "Do it, Ser
Duncan. Any knight can make a knight".
That being said, your question is valid. Do people believe that a person was knighted? This is why it is customary to perform Knighting ceremony in front of Witnesses.
When Ser Duncan the Tall claimed to be a knight, The Steward of Ashford, a man named Plummer, instantly picked on that and pointed out he should have had his knighthood in front of a Septon and Witnesses. Quoting from The Hedge Knight:
“Hmpf.” The man Plummer rubbed his nose. “Any knight can make a
knight, it is true, though it is more customary to stand a vigil and
be anointed by a septon before taking your vows. Were there any
witnesses to your dubbing?”
There are four paths to obtaining Knighthood:
1. The Regular Path
This path is followed by the nobility and chivalry of Southern Kingdoms who are of general Andal descent and follow the faith of Seven. It involves following steps:
- Become a Page of a Knight as a child. Run simple errands and be trained in basic martial Arts.
- Become squire of a knight. Learn about weapons and equipment. Learn more advanced martial arts. Accompany your master to battle and fight if need be.
- Be knighted by your master when he deems you are ready. You will have to stand a vigil in a sept and be anointed by a Septon but it is just customary, not required. Witnesses should be present but that is also only customary to maintain some proof of some person's knighthood.
2. Valor-in-Battle Path
The second path does not involve the long training of regular path. If you show extra ordinary valor in a battle, you can be knighted by your King or your Liege lord (Ser Jorah Mormont was knighted for his valor in Siege of Pyke during Balon Greyjoy's 1st Rebellion). If they are not knights, they might ask some other knight to knight you (Daenerys asked Ser Jorah to knight Ser Barristan Selmy, unaware of the fact that Selmy was already a legendary knight).
3. Buy-the-knighthood path
Third path is the easiest. You just give a knight something he wants and in return you can demand knighthood. Ser Glendon Flowers bought his knighthood from Ser Morgan Dunstable at price of his sister's maidenhead. Ser Morgan accepted the offer and knighted Glendon in front of a dozen witnesses.
4. Perform a great deed
If you perform a great deed for some noble, he may knight you in reward. Ser Davos Seaworth was knighted by Stannis Baratheon for saving the garrison of Stormsend from death by starvation.
5. Marry the heir apparent to the throne
Ser Laenor Velaryon was hastily granted Knighthood before his marriage to Princess of Dragonstone, Rhaenyra Targaryen since it was deemed necessary by the court that the Prince Consort must be a knight.
6. Ask for it as a last boon
You can ask for Knighthood as your last wish before execution. Trystane Truefyre did so and died a knight.
In all these methods, One thing is common. No matter what path you choose, some witnesses are always customary. It is those witnesses who are then contacted if a real legal proof of someone's knighthood is needed. e.g. if a Knight is accused of a crime and demands a trial by combat, The accusing authority will be within its rights to demand proof of knighthood. The burden of acquiring the proof which is mostly someone vouching for their status is on the accused.
How do Common people react to such claims?
As already stated by KutuluMike, as far as common people are concerned, if someone is wearing an armour and riding a horse, they are okay with giving them the courtesy of calling "Ser". Brienne of Tarth was mistakenly called Ser many times despite not being a Knight. If you look like a knight and can act like a knight, you can claim you are a knight but it will be very difficult for you to prove if some proper authority demands a proof or testimony.
But if you look haggard and poor, even a horse and armor won't give credence to your claim. Knights are usually sons of Noble lords and thus are well-to-do. Hedge Knights do exist as well but they are generally viewed with suspicion. Quoting from The Mystery Knight, this is what an innkeep had to say about poor knights:
"The lake is full of fish and you will find some other rogues camped
down by the stumps. Hedge Knights, If you believe them". Her tone
made it clear that she did not.
So if you are unknown, it really depends on the other person whether they consider you a knight or not.
How to make it stick
There is only one way to do it. Be Famous. There are different ways of becoming famous:
- Westerosi people love to follow tourneys and knights. Knights who show talent in tourneys are sort of comparable to celebrities in our world. So get your jousting game up. Barristan Selmy was only a child when he sneaked in to ride in a tourney. Prince of Dragonflies, Duncan Targaryen unseated him and gave him the epithet "The Bold". Selmy was known as The Bold for the rest of his life, even after his real knighthood.
- Robber Knights are also sort of celebrities. You can become an outlaw knight and win commons like Brotherhood of the Kingswood did. You will be famous in no time.
- Perform valiant acts in battle and form comradeship. If you fight well and maintain good relations with warriors coming from all parts of the Kingdom, you will likely create a reputation for yourself. When Jaime was investigating knighthood of Ser Kettleblack, first questions he asked were about the tourney Kettleblack had rode in and battles he had fought in.
- Excel at skill at arms and catch attention of some lord using option 1 and 3. Eventually, if you are good enough, word will reach to the King and you might get a white cloak. Then your name will be known to everyone in the Kingdoms.
- Make sure that you do get a decent number of witnesses to view your knighting ceremony. If you do, at least in that locale you won't have any troubles with getting the title "Ser" from peasants.
If you are famous, no one will doubt your knighthood.
For example:
Barristan Selmy goes to an inn.
Barristan: Hullo, I am Barristan Selmy.
Innkeep: Seven hells, It's Ser Barristan the Bold. I gotta get a
portrait drawn with you, Ser. Drinks on the house.