Johannes of Palermo was a scholar in Frederick II's court. Frederick was aware of Fibonacci's work, and perhaps even an admirer. In 1225 when Frederick's court met in Pisa, Fibonacci was invited to demonstrate his works. I can't find a source for when exactly Johannes of Palermo posed his problems, but the two men certainly met in Pisa and Johannes posed his problems directly at Fibonacci:
A meeting was arranged between Fibonacci and Frederick at the Emperor's palazzo in Pisa, Frederick bringing with him an imposing retinue of people and animals. Frederick, who was about 30 years old, is described as "athletic-looking and of medium height, with reddish-blond hair and piercing blue eyes which are said to have made his courtiers tremble".
Mathematical questions for Fibonacci to solve were proposed by a scholar, Master John of Palermo. According to some writers, a mathematical tournament between Fibonacci and other mathematicians took place, but this does not seem to have been the case. Three of these problems are given later when I deal with Fibonacci's mathematical writings. At the time of his meeting with Frederick in the 1220's, Fibonacci was probably at the height of his prowess.
Source: 800 years young, A. F. Horadam, Department of Mathematics, University of New England
As for an example of the problem:
In Flos Fibonacci gives an accurate approximation to a root of 10x + 2x2 + x3 = 20, one of the problems that he was challenged to solve by Johannes of Palermo. This problem was not made up by Johannes of Palermo, rather he took it from Omar Khayyam's algebra book where it is solved by means of the intersection of a circle and a hyperbola. Fibonacci proves that the root of the equation is neither an integer nor a fraction, nor the square root of a fraction. He then continues:-
And because it was not possible to solve this equation in any other of the above ways, I worked to reduce the solution to an approximation.
Without explaining his methods, Fibonacci then gives the approximate solution in sexagesimal notation as 220.127.116.11.33.4.40 (this is written to base 60, so it is 1 + 22/60 + 7/602 + 42/603 + ...). This converts to the decimal 1.3688081075 which is correct to nine decimal places, a remarkable achievement.
Source: Leonardo Pisano Fibonacci (short biography), School of Mathematics and Statistics, University of St Andrews, Scotland
There is another example from Flos in the source of my first quote, but unfortunately without Fibonacci's solution. Perhaps you would like to try and solve it on your own? ;)