I have just started using KiCAD (with no other experience e.g. in Eagle). I was basically able to put together a schematic and layout a board but I am struggling with some footprints. How would I search for, e.g., a footprint for these? Can I expect footprints somewhere in the library for most components or is creating my own a common task?
I use Eagle and, despite its huge libraries, most of the time I prefer to create my own footprints since I can adjust them to suit my needs.
For example, I usually use a 0.25 grid and the 0603 capacitor as it is on the library doesn't allow a 0.25 mm trace to pass between pads with a 0.25 mm clearance without warnings so I redesigned the footprint so it generates no warnings.
Besides that, it is common not to find the components you need on the libraries or to make slight modifications to adjust them to your design preferences.
Make your own footprint from data available in the data sheet for the component you're using. In the long run, you'll spend more time making sure libraries you download are accurate than you would spend just making your own correct footprint.
There are a lot of existing module and footprint libraries for KiCAD, but sometimes they may be difficult to locate. Here's the default starting point: http://www.kicadlib.org/. On the top of the page, there's also a link to a KiCAD library search engine.
Another option is converting existing libraries from another CAD tool to KiCAD format. Particularly, there's an Eagle2Kicad conversion script.
Regardless of how you obtain a library, it's always a good practice to double-check the particular footprint against the component in your hand. For some components, there's just too much variation (and mini-USB receptacles are among those).