My first published game has a map of seven hexagonal tiles, so I have some experience with this.
If you must have hex tiles (e.g. a case where the board layout is user-generated as in the 4x game E C L I P S E, not fixed as in Catan or as in my game), then I would buy a bunch of blank tiles from The Game Crafter or Amazon. Our earliest prototypes used something similar (though made of a thicker composite material).
With tiles in hand, just print square icons and tape them to the tiles. For that matter, you could just write freehand on the tiles.
If you can get away with a using a pre-determined grid layout, then that will be much less expensive. Just print an appropriate hex grid, and use square or circular tokens to randomly distribute the hexes on the board. We used this in later prototypes, and eventually in the published version of my game.
In any case, I would strongly advise against cutting out a lot of hexagons. It's unwieldy! Make some icons and send the files to The Game Crafter or to Print and Play Productions. They are much better at cutting :)