My wife finds that the marinated tofu we add to our pasta tastes pretty similar to meat (I am vegetarian but she is not, so I wouldn't know, but I take her word for it). When a recipe contains fish, what might be some vegetarian (and perhaps vegan) foodstuffs that may be suitable as a substitute? Suitable in the sense of: fits taste-wise, perhaps similar taste and substance, similar nutritional value.
A lot of the fishy taste comes from the Omega 3 fats which are abundant in fish. Fortunately, fish is not the only source of them, and you can substitute them.
The best substitute is probably seaweed. Take some white tofu and marinate it in seaweed. Ideally, add the seaweed to the sauce later.
Use linseed oil and add it to your sauces. It contains Omega 3 fats and also has a taste that can resemble fish.
I personally find that the smoked garlic paste by Biona (which you can buy in organic shops in the UK and Germany) tastes a bit like fish, so marinate tofu in it and/or add it to the sauce.
As a supplement to the great answer by Zanna - seaweed is a great way to fake fishy sea flavour - you can sometimes fake the flavours around fish without actually having fish.
For example, a store-bought fish cake might be mashed potato, dill, and fish, fried and breaded. Making the same thing without fish, but with the dill, can be surprisingly close. A veggie or vegan tartar sauce can help trick you a little further.
To add to the other answers, depending on where you are located, it could be worth checking out Quorn Fishless Fingers product. These are vegan and very fish-like. Unfortunately, they come already breadcrumbed and so may not be a great fit for many recipes.
If Quorn is not sold in your country, I used to use tofu to substitute for fishy taste before I discovered these, so that could be worth looking into.
I make vegetarian "fish and chips" by cutting halloumi into cubes, dipping it in batter and then deep frying it.
You can make a batter from from sparkling water, flour and optionally egg. Some people use plain water and a little baking powder instead of sparkling water.
Add chips and mushy peas to get vegetarian "fish" chips and peas.
Something that really reminds me of the taste and texture of fish is banana flowers. They contain vitamins a c and e as well as potassium and fiber. This dish is common in southeast Asia. The taste is so similar I have to ask every time I eat it.
It is commonly boiled to make it soft and you can then treat it like any other meat when it comes to seasoning. You don't need to bake it long since it is not meat and does not need much cooking.