A Certificate of Authenticity or COA is a piece of paper (certificate) given to a buyer along with an artwork as proof that the piece is authentic. Typical information given is the title of the artwork, the medium, size, date of creation, edition size and edition number (for limited edition prints), plus details of who has issued the certificate (artist, gallery, art assessor). There is no official organization that issues certificates of authenticity and, as with any documentation, COAs can be faked, as an art buyer you should check who issued it.
As a painter creating your own COAs, you would include a space to sign the certificate plus your contact details and probably a line about your retaining copyright of the painting. It doesn't need to be a huge fancy certificate full of gold embossing, it can be as simple and straightforward as you like. What's important is it does its job and looks professional. A small certificate could be stuck to the back of a painting, or attached in an envelope.