Several vendors require Crucible and Vanguard marks for purchasing certain items, but the tooltips say nothing about how to get them. How and when do I get these marks?
Crucible Marks are obtained by anything and everything PvP. The amount you get varies on performance and game mode.
Vanguard Marks you get by doing the Strike playlist (opens at around level 17). You can also gain marks at a much slower rate by doing other PvE interactions, like patrolling and random events that appear during patrols. The amount you get varies on the Strike Difficulty selection you chose.
Both kinds of Marks have a weekly earn limit of 100 before you can gain more again. The time renews on Tuesdays, IIRC.