General answer to the question from Steam
Profile icons typically unlock when you play a character a certain amount of times in Arcade Versus or Online mode.
You can also unlock a new icon when you complete 5 of any given characters' trials getting you an icon based around them (such as a sunburst insignia for Kyo or the red-and-yellow pattern on Billy's bandanna for his.)
Chibi character icons can be unlocked when you beat Time Attack as that respective character.