Consider the following function: $f: \mathbb{R}^n\rightarrow\mathbb{R}$ $$f(x)=\max_{p\in\mathcal{P}} x^Tp$$ where $\mathcal{P}\in\mathbb{R}^n$ is a nonempty and compact set.
It is easy to see that $f(x)$ is a piecewise convex function but is it true that $f(x)$ has gradients almost everywhere? Any references and counterexamples are very welcome.
It is not actually the case that $f$ is always a piecewise convex function. It depends completely on the set $\mathcal{P}$.
Onto your question, I assume by "almost everywhere" you mean that the set of non-differentiable points has measure $0$.
So, if $\mathcal{P}$ has measure $0$, then $f$ is differentiable "almost everywhere".
If $\mathcal{P}$ has non-zero measure, then it may be the case that $g$ is non-differentiable on a set with non-zero measure (some subset of $\mathcal{P}$ that has non-zero measure, perhaps $\mathcal{P}$ itself).